CSci 242. Algorithms and Data Structures

 

 

Term: Spring 2017.

Class Hours: 11:00 - 12:15 PM, TR

Room: 106 Streibel

 

Instructor: Dr. M. Eunjin Kim

E-mail: ejkim@cs.und.edu; Send an email at eZ LMS.

Office: 215 Streibel

Phone: (701)777-3338

Office Hours: 12:15 - 12:45 PM, TR and 1:00 - 3:30 PM Wed.

 

TA: Debesh Adhikari (debesh.adhikari@my.und.edu)

TA's Office Hour: 1:30 - 3:30 PM, Wed. (Rm. 219)

 

Recitation Class: 6:00 PM, Thr. (Rm. 238)

 

Prerequisites:

Csci 161 Computer Science II: Java

Math 208: Discrete Mathematics

 

Required Textbook:

Algorithm Design and Applications

Michael T. Goodrich, Roberto Tamassia

Wiley, October 2014.

 

Recommended Book:

Intro Introduction to Algorithms, 3rd ed.

Thomas H. Cormen et.al.

The MIT Press, 2009.

 

Data Structures and Algorithms in Java 6/e

Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser

Wiley, January 2014.

 

Course Webpage:

https://learn.aero.und.edu/index.asp.

You need to create a new account at eZ LMS if you didn't have it.

Grade Policy:

Midterm: Part I & II - 20%

Final Exam: Part III & IV (& VI). - 25%

Assignments & Quizzes: 25%

Project: 25%

Attendance: 5%

 

 

Final Grade Policy:

 

Midterm = y1; Your Midterm Score = x1;

Final Exam = y2; Your Final Exam Score = x2;

HW/Q Total = y3: Your Total HW Score = x3:

Project = y4; Your Project Score = x4;

Attendance = y5. Your Attendance = x5.

 

Your Total of Final Grade = x1 / y1*200 + x2 / y2*250 + x3 / y3*250 + x4 / y4*250 + x5 / y5*50

 

A: 900 - 1000

B: 800 - 899

C: 700 - 799

D: 600 - 699

F: 0 - 599

 

 

FINAL EXAM:

 

1:000 PM, May 9th (Tue.) 2017.

 

 

 

COURSE DESCRIPTION:

 

The data structures and algorithms are the basic elements for problem solving and further build the large and complex software artifacts. This course provides the students with the basic theory/implementation of algorithms, the fundamental data structures, algorithm design techniques, and the analysis of algorithms. The topics include: data structures, such as trees, priority queue, heap, hash table and graph; the advanced algorithms such as sorting algorithms and graph algorithms; the algorithm design techniques such as divide-and-conquer, dynamic programming and greedy method; and the asymptotic analysis of algorithm in terms of the order of growth of the function such as upper bound (O), lower bound (W) and tight bound (Q). Thus, the students are expected to have a good understanding of various data structures, algorithms for problem solving, algorithm design techniques and its analysis skill enough to design the correct and efficient algorithms for complex software artifacts.

 

 

ABET Outcome:

a)   An ability to apply knowledge of computing and mathematics appropriate to the discipline.

i) An ability to use current techniques, skills, and tools necessary for computing practice.

j) An ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices.

 

SELECTED TOPICS:

 

0.      Preface

 

Chap. 1. Algorithms Analysis

 

I. Data Structures

 

Chap. 2. Basic Data Structures

Chap. 3. Binary Search Trees

Chap. 4. Balanced Binary Search Trees

Chap. 5. Priority Queues and Heaps

Chap. 6.Hash Tables

Chap. 7.Union-Find Structures

 

 

II. Sorting and Selection

 

Chap. 8. Merge-Sort and Quick-Sort

Chap. 9. Fast Sorting and Selection

 

III. Fundamental Techniques

 

Chap. 10. The Greedy Method

Chap. 11. Divide-and-Conquer

Chap. 12. Dynamic Programming

Chap. 13. Graphs and Traversals

 

IV. Graph Algorithms

 

Chap. 14. Shortest Paths

Chap. 15. Minimum Spanning Trees

 

VI. Additional Topics

 

Chap. 20. B-Trees and External Memory