CSC 220 - Syllabus

91ÒùĸÊÓƵ • Grove School of Engineering • Computer Science Department • Course Syllabus

Course number

CSc 22000

Course name

Algorithms

Credits & hours

3 cr., 3 hr.

Course coordinator

Prof. Peter Brass

 

Textbook, title, author, and year

  • No required textbook; note-taking required; recommend buy a used copy of, e.g., the Cormen-Rivest-Leiserson book; but all algorithms textbook since the 1990s are similar
  • Other supplemental materials: wikipedia pages exist for all algorithms discussed in this class, and are recommended. Do not rely on code published in online; it is frequently bad

Specific course information

  • Algorithms, their analysis and implementations. Asymptotic Analysis (O-Notation) and Recurrence Relations as applied to the worst-case runtime of algorithms. Implementation projects done individually, with test code provided; midterm and final exams.
  • Prereq.: CSc 21200
  • Required course

Specific goals for the course and Relationship to student outcomes

 

1

2

3

4

5

6

a. the student acquires knowledge of how to specify and determine algorithm behavior (worst-case runtime, expected runtime of randomized algorithms; Asymptotic Analysis with O and Omega; Analysis of Recursions)

R

    

P

b. the student acquires knowledge of how to compare the advantages and limitations of distinct algorithms that perform the same task (compare sorting algorithms: bubble-, insertion-, merge-, heap-, quick-, radixsort; compare minimum spanning tree algorithms: Prim's and Kruskal's Algorithm; compare BFS and DFS)

R

    

P

c. the student acquires knowledge of some classes of algorithmic paradigms, e.g., divide-and-conquer, randomized, greedy, use of data structures, etc.(mergesort for divide-and-conquer, quicksort for randomized, heapsort and Prim's algorithm for use of data structures, Kruskal's algorithm for greedy)

R

    

P

I - introductory-level; R - reinforced-level; P - program-level

Brief list of topics to be covered

Seq.

Topics

1

Algorithms and Problems: sorting; Introduction O-Notation; bubblesort; insertion sort

2

Divide-and-Conquer; Mergesort; Analysis of Recursions

3

Randomized Algorithms; Quicksort; Analysis of Expected Runtime

4

Data Structures; Heapsort

5

Lower Bound: Decision Tree Bound for Comparison-Based Sorting

6

Radix Sort: Linear Time Sorting that is not Comparison-Based

7

Search Trees: Basic Find, Insert, and Delete; Rotations

8

Height-Balanced Search Trees; Analysis and Rebalancing Algorithm

9

Midterm Preparation, Review, and Midterm Exam

10

Graph exploration, DFS and BFS

11

Shortest Paths; Dijkstra's Algorithm

12

Minimum Spanning Trees; Prim's and Kruskal's Algorithm

13

Maximum Flow; Ford-Fulkerson algorithm, Max-Flow-Min-Cut-Algorithm

14

Dynamic Programming Algorithms

15

Arithmetic on Long Integers; Karatsuba-Ofen Algorithm

16

String Matching; Knuth-Morris-Pratt Algorithm

17

Complexity Classes P, NP; NP-completeness; SAT Problem is NP-Complete

18

Final Exam Preparation; Review; Final Exam

 

Last Updated: 05/22/2018 19:50