Design and Analysis of Algorithms (COMPSCI 308)

Fall 2022-2023 / Session 2 (7 weeks, 35 hours)

Course Period: October 24 - December 8, 2022

  • Lectures: Monday / Tuesday / Wednesday / Thursday @ 16:15-17:30 (Classroom: IB 1053 + Zoom)
Instructor: Mustafa MISIR (Office: CC 3019), mustafa.misir [at] dukekunshan.edu.cn   /   mm940 [at] duke.edu
Teaching Assistant: TBA (Office: TBA), TBA

An algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output. An algorithm can also be viewed as a tool for solving a well-specified computational problem. The statement of the problem specifies in general terms the desired input/output relationship. The algorithm describes a specific computational procedure for achieving that input/output relationship.

After having a target problem, the next step is to design an algorithm that can address the target problem. Algorithm design is a coherent discipline-one needs a specific set of concepts to define, a computational problem and a specific set of tools to design an optimal algorithm to solve it. Designing the right algorithm for a given application is a major creative act-that of taking a problem and pulling a solution out of the ether. The space of choices you can make in algorithm design is enormous, leaving you plenty of freedom.

Solely designing algorithms may not be a proper approach to solve a specific problem. Understanding their behavioral characteristics together with their strengths and weaknesses is critical. Algorithm analysis is investigated for this purpose, in particular, for determining how much of a resource, such as time or memory, an algorithm uses as a function of some characteristic of the input to the algorithm, usually the size of the input.

This course will touch all the major algorithm design and analysis steps while taking data structures into account. All the relevant concepts will be exemplified through existing algorithms and problems besides implementing algorithms in Python. To be specific, the design and analysis of efficient algorithms including sorting, searching, dynamic programming, graph algorithms, nondeterministic algorithms and computationally hard problems and other related topics will be studied.

This course will be carried out in line with the DKU's animating principles. In particular, Collaborative Problem Solving, Research and Practice and Lucid Communication will be directly involved with this course while touching the Independence and Creativity aspect. The course will be primarily executed through in-class quick quizzes, in-class individual / group discussions and weekly assignments.

By the end of this course, you will be able to:
  1. design efficient and effective algorithms of varying types
  2. implement algorithms in consideration of the problem requirements and computational resources
  3. utilize appropriate data structures while developing algorithms
  4. introduce new algorithmic solutions for new problems
  5. evaluate the theoretical boundaries of given algorithms
  6. analyze the behaviour and performance of given algorithms, referring to their strengths and weaknesses
  7. identify the resemblance between different problems, leading to problem hardness analysis
>> Follow Sakai for announcements and discussions

Pre-requisites

  • COMPSCI 201: Introduction to Programming and Data Structures
  • COMPSCI 203: Discrete Math for Computer Science or MATH 205 / 206: Probability and Statistics

Anti-requisites

  • COMPSCI 301: Algorithms and Databases

The following chart shows how COMPSCI 308 fits to the DKU curriculum, where the abbreviations indicate the course types, i.e. D: Divisional, DF: Divisional Foundation, ID: Interdisciplinary and E: Elective. Refer to the DKU Undergraduate Bulletin for more details.



Reference Books

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (3rd Edition), 2009, MIT Press (Free Book: ProQuest - Duke U.) [ Lecture Slides ]

Supplementary Books: Algorithms + Python:

Lecture Notes / Slides


Grading

  • Homework Assignments: 20%
    • Mathematical, Conceptual, or Programming related
    • Submit on Sakai; 7 in total
  • Quizzes: 10%
  • Weekly Journals: 10%
    • Each week, write a page or so about what you have learned
    • Submit on Sakai; 2 points off for each missing journal, capped at 10
  • Midterm: 25%
  • Final: 35%

Reference Courses


Other Books

Quick / Easy Reads:
Python Programming:
Foundations of Computer Science:

Other Materials / Resources

Cheat Sheets: Algorithm Visualization / Animation: Miscellaneous: General: