1



TEACHING PLANCourse Title:Design and Analysis of AlgorithmsCourse Code:CSC-305Credit:3Contact Hours:3 hours lecture per weekSemester:Semester 6 (Fall 2014)Prerequisite:Data Structure and Algorithm (CSC-260)Instructor:Engr. Dr. Sohaib Ahmed/Mr. Khawaja MohiuddinObjectives:The main objective of this course is to study paradigms and approaches used to analyze and design algorithms and to appreciate the impact of algorithm design in practice. Upon completion of this course, students will be able to do the following:Demonstrate a familiarity with major algorithms and data structuresAnalyze the asymptotic performance of the algorithmsImplement important algorithmic design paradigms and methods of analysisSynopsis:The major areas of study include Sorting Algorithms, String Algorithms, Recursion, Searching, Hashing, Greedy Methods, Dynamic Programming, Natural Algorithms, Randomized and Approximate Algorithms.Lecture Schedule:DATEWEEKTOPICS/SUBTOPICSASSIGNMENTS/ QUIZZESREMARKS01/09/2014 – 07/09/201401INTRODUCTIONOverview of the course, Course policies, Marks distribution structure, Essential mathematical background Topic “Essential mathematical background” is taken fromDave (2014)08/09/2014 – 14/09/201402ALGORITHM BASICSBasic concerns, What is algorithm, Five distinct areas in the study of algorithms, Algorithms and data structures, Qualitative and quantitative aspects of a good algorithm, Algorithm features; correctness, maintainability and efficiency, Pseudo-codeAll topics are taken from Chapter 1 ofDave (2014) except “Pseudo-code”, which is taken from Rod(2013)15/09/2014 – 21/09/201403PROBLEM SOLVING WITH A COMPUTERThe steps required for a problem solving with a computer; problem definition, development of a model, design of the algorithm, checking the correctness of the algorithm, implementation in some programming languages, analysis and study of the complexity of the algorithm, program testing, preparation of document, Numerical algorithms; finding the square root of a number, smaller divisor of an integer, finding prime numbers.All topics are taken from the Chapter 2 of Dave (2014) except “finding prime numbers”, which is taken from Rod (2013) 22/09/2014 – 28/09/201404TIME COMPLEXITYTime complexity, Asymptotic notations; Big-O, Small-o, Big-omega and Big-Theta, Rules of Big-O notation, Common runtime functionsFrom Chapter 1 of Rod (2013)29/09/2014 – 05/10/201405SORTING ALGORITHMSO(N2) Algorithms; insertionsort, selectionsort and bubblesort, O(N log N) Algorithms; heapsort, Assignment # 1 (Individual)From Chapter 6 of Rod (2013)06/10/2014 – 12/10/201406SORTING ALGORITHMSQuicksort, Mergesort,Countingsort, Bucketsort, Summary of complexity and characteristics of sorting algorithms Quiz # 1From Chapter 6 of Rod (2013)13/10/2014 – 19/10/201407SEARCHINGLinear search, Binary search, Interpolation search, Traversal, Types of traversal: In-order traversal, pre-order traversal and post-order traversal, Breadth first search (BFS), Depth first search (DFS)Linear, Binary and Interpolation search topics are taken from Chapter 7 of Rod (2013) and others are taken from Chapter 12 of Dave (2014)20/10/2014 – 26/10/201408HASHINGHash table fundamentals, Chaining, Open Addressing: Linear probing, Quadratic probing, Pseudorandom probing, Double hashing, Ordered hashingAssignment # 2 (Individual Assignment)From Chapter 8 ofRod (2013)27/10/2014 – 02/11/201409Mid Term Examination03/11/2014 – 09/11/201410RECURSIONBasic algorithms: Factorial, Fibonacci numbers, Tower of Hanoi, Backtracking Algorithms: Eight Queens Problem, Knight’s tour.From Chapter 9 ofRod (2013)10/11/2014 – 16/11/201411STRING ALGORITHMSPattern matching, DFAs, Building DFAs for regular expressions, NFAs, String searchingFrom Chapter 15 ofRod (2013)17/11/2014 – 23/11/201412DIVIDE AND CONQUERIntroduction, A multiplication algorithm and its analysis, Application to graphics algorithms: Triangulation, Convex Hulls, Where divide and conquer fails Quiz # 2From Chapter 9 of Dave (2014)24/11/2014 – 30/11/201413GREEDY METHODSIntroduction, Knapsack problem, Dijkstra’s shortest path algorithm, Optimal merge patternsFrom Chapter 10 of Dave (2014)01/12/2014 – 07/12/201414DYNAMIC PROGRAMMINGIntroduction, Rod cutting problem, Travelling salesman problem, Matrix multiplicationFrom Chapter 11 of Dave (2014)08/12/2014 – 14/12/201415NATURAL ALGORITHMSGenetic algorithms, Simulated annealing, Artificial neural networks Quiz # 3From Chapter 13 of Dave (2014)15/12/2014 – 21/12/201416RANDOMIZED ALGORITHMSSimple randomized algorithm, Reasons for using randomized algorithms, Probability theory, Generation of large prime numbersAssignment # 3 (Group Assignment)From Chapter 19 of Dave (2014)22/12/2014 – 28/12/201417Revision29/12/2014 – 04/01/201518Final ExaminationCourse Evaluation:Course Work: 30%Mid Term: 20%Final Exam: 50%Text Book: Himanshu, D. P. (2014). Design and Analysis of Algorithms (2nd ed.). Pearson (New Delhi).Reference Books:Stephens, R. (2013). Essential Algorithms: A Practical Approach to Computer Algorithms. Wiley BIBLIOGRAPHY Cormen, T. H. (2012). Introduction to Algorithms (3rd ed.). PHI Learning.Course Policy:Homework (Assignments)Assignments are due at the beginning of classLate assignments will not be acceptedAll works have to be done independently except in case of group assignmentsStudents handing in similar assignments will receive a grade of 0 (ZERO) and face possible disciplinary actions.Makeup ExamsIn accordance with university regulations, i.e. students should bring a valid excuse authenticated through valid channels immediately within first week after the exam. Otherwise they will be considered absent and no makeup exam for them. AttendanceStudents are expected to attend all classesIf a student misses 10 hours from classes without an acceptable reason, the student will be barred from the final exams.Code of ConductThe assignments, quizzes and exams need to be done individually. Copying of another student's work or code, even if changes are subsequently made, is inappropriate, and such work or code will not be accepted. The University has very clear guidelines for academic misconduct, and they will be enforced in this class. However, in case of group assignments, copying of another group’s work or code, even if changes are subsequently made, is inappropriate, and such work or code will not be accepted.Cell PhoneCell phones are restricted during class. Cell phones must be turned off during the lecture. If your cell phone rings during the class, you may be asked to leave.*It is acknowledged that the objectives, synopsis of the course and distributions of examination marks will not be changed in the framework of the course as certified.______________________ ___________________________Signature of InstructorValidated by Head of DepartmentDate:Date: ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download