CSci 242. Algorithms and Data Structures



Term: Fall 2017.

Class Hours: 11:00 - 12:15 PM, T/R

Room: 106 Streibel


Instructor: Dr. M. Eunjin Kim


Office: 215 Streibel

Phone: (701)777-3338

Office Hours: 1:00 - 3:30 PM Wed.


TA: TBD (RM. 219) (

TA's Office Hour: ? - ?? PM, TBD. (Rm. 219)


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



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

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:

Grade Policy:

Midterm: Part I & II - 25 (or 20)%

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

Assignments & Quizzes: 25 (or 20)%

Project: 25 (or 20)%

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*250 (or 200) + x2 / y2*250 (or) + x3 / y3*250 (or) + x4 / y4*250 (or) + x5 / y5*50


A: 900 - 1000

B: 800 - 899

C: 700 - 799

D: 600 - 699

F: 0 - 599





1:000 PM, December 14th (Thr.) 2017.






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.




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