CSC 306 + Lab: Algorithm

Offered Under: B.Sc. in Computer Science (CSC)
Description

Techniques and principles of algorithms design including divide-and-conquer and greedy algorithms. Complexity (worst and average case) analysis and their associated asymptotic notations (Theta, Big O, Omega). Iterative sorting algorithms: Bubble sort, insertion sort. Recursive sorting: merge sort, quick sort, heap sort. Sorting in linear time: counting/radix sort. Decision tree analysis: N*logN bound on comparison based sorting.  Algorithms for graph problems: Shortest path (Dijkstra), minimum spanning trees (MST algorithms: Kruskal, Prim). Hashing. Discussion on NP-class problems (e.g. Travelling Salesman Problem).



Course Type Major
Credit Hour 3
Lecture Hour 60
Expected Outcome(s):
  • Students will learn methods for designing efficient algorithms, evaluating their performance, and ways of establishing precise limits on the possible effectiveness of classes of algorithms
  • They will learn standard algorithms for fundamental problems.


Grading Policy:

Biweekly Quiz, One Midterm Exam, One Final Exam, Project


Letter Grade Marks Grade Point
A 90 - 100 4.00
A- 85 - 89 3.70
B+ 80 - 84 3.30
B 75 - 79 3.00
B- 70 - 74 2.70
C+ 65 - 69 2.30
C 60 - 64 2.00
C- 55 - 59 1.70
D+ 50 - 54 1.30
D 45 - 49 4.00
F 00 - 44 4.00