COSC 351A
Algorithm Design & Analysis

Spring 2021

Syllabus

Instructor

David A. Sykes, Ph.D.

Class sessions

TR 1:00-2:20 P.M. in DB 102

Office hours

MWF 2:00-3:30 P.M.
TR 9:00-10:45 A.M., 2:30-3:30 P.M.
Or by appointment. Or happenstance.

Telephone / e-mail

(864) 597-4524 / sykesda@wofford.edu

A study of the design and analysis of algorithms for solving problems, including dynamic programming, divide-and-conquer algorithms, greedy algorithms, graph algorithms, and search algorithms. Evaluation of time-space trade-offs. Prerequisites: (COSC 240 or MATH 235) and COSC 350.

By the end of the course, you should be able to:

  1. Understand general algorithm strategies: brute-force, greedy, divide and conquer, dynamic programming, randomized, branch-and-bound, and recursive backtracking.
  2. Solve problems by applying suitable strategies.
  3. Use standard graph algorithms, including those to find the shortest path and a spanning tree.
  4. Write programs in C and in C++.
  5. Use components of the C standard library and the C++ Standard Template Library (STL) based on reading library documentation.
  6. Understand the concepts of encapsulation, inheritance, and polymorphism in the context of C++.
  7. Understand the concepts of template and operator overloading in C++.
  8. Write a technical paper using a Microsoft Word template or a LaTeX template.
Required textbook

textbook cover Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin, ©2012. ISBN 978-0132316811.

Web resources

We will use three websites regularly:

  1. This term we will be using Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates and me. Rather than emailing questions to me, post your questions on Piazza. Sign up.

    Note: You may post or respond to a post anonymously. Be aware that your post will be anonymous to classmates but not to me.

  2. Moodle. You will submit some assignments in Moodle. Your grades will be recorded in Moodle.

    Note: The cumulative grade shown in Moodle should reflect your final weighted score under Method #1 [see below]. Occasionally, the complexity of the Moodle grade book setup will confound me and I might set it up incorrectly. If you notice a problem, please let me know and I will correct it.

  3. Mimir Classroom. You will submit projects, complete homework exercises, and take tests in Mimir Classroom. You can even use it to code your web pages. You need to create a free account. Use your Wofford email address for the account.

Hardware and software

You will need a computer in order to work on assignments and access the websites we will use. A laptop computer that you can bring to class is ideal. The computer needs a web browser. You will be able to write C and C++ code using the Mimir IDE.

You will also need to use Microsoft Word to create a paper for this course. You can download it from Wofford College | MS Office Download.

Your grade for the course will be based on a weighted average of scores for weekly quizzes, programming projects, and a paper and presentation (semester-long project). The usual grading scale applies: 93–100: A, 90–92: A-, 87–89: B+, 83–86: B, 80–82: B-, 77–79: C+, 73–76: C, 70–72: C-, 60–69: D, 0–59: F.

Component Score Weight
Weekly quizzes 50%
Programming projects 30%
Paper and presentation 20%
TOTAL 100%
Weekly quizzes

There will be twelve 5-point quizzes, one given each Wednesday, except for the Wednesday of the first week of classes. A weekly quiz encourages you to keep up with the work and helps both you and me assess how well you understand the topics we are covering.

Quizzes will be conducted as follows.

  1. A quiz will start at 1:30 P.M. on Wednesdays. All papers must be turned in when time is called at 1:45 P.M. At that time you may leave the classroom. If you have an accommodation that calls for extra time, you may continue after time is called and others leave.
  2. Each quiz is worth 5 points. Each of five problems is worth one point. An answer to a problem must be completely correct to be awarded a point. No partial credit will be given. You must show your work for any problem that requires a sequence of steps to answer in order to receive a point for that problem.
  3. A “rework” copy of the quiz will be made available. You have an option to rework the problems on the quiz and then submit your answers by the start of class on the following Friday. If all of the answers on your reworked quiz are correct, then you will earn back half of the points that you missed on the Thursday quiz—for example, if you got 2 on a Wednesday quiz and 5 on the rework quiz, then 3.5 will be recorded as the score for that quiz. Note: You may get all of the help you need on the rework, including help from me, except you may not post questions about the quiz at Piazza or other web forum.

Cell phones, calculators, computer applications, web resources, or other people may be used during a quiz except for ones you are directed to use.

Programming projects

Programming projects give you practical experience with what we are covering in class. Programming projects will comprise 30% of your final grade.

Point values for projects will vary and will reflect the level of challenge. More challenging projects will have higher point values. Your programming projects score will be computed as the percentage of points earned times 30. That is, I will add up all of the points you earned for programming projects and divide that by the number of points that you could have earned and then multiply that ratio by 30.

To get a perfect score on a project, your submission must satisfy all of the requirements set forth in the project’s description and be submitted before the deadline. Often there will be a rubric available in Moodle. If you’d like to incorporate more than the required features in your code, then please do!

Paper and presentation

The paper and presentation will be worth 20 points (20% of your grade). You will receive several scores during the semester: a score for a first draft, a score for your review of another student’s first draft, a score for your second draft, and a score for the final draft.

Component Score Weight
First draft 6 points
Second draft 6 points
Final draft 8 points
TOTAL 20 points
Homework

Homework will be assigned regularly, but will not be collected and graded. Bring written answers to assigned problems to class with you. I encourage you to work on homework assignments with other students in the class.

Class meetings

We are fortunate to be meeting in a classroom that can accommodate all of us even with appropriate social distancing. Consequently, all of us can attend class meetings in person starting with the second week of classes. The first week classes will meet remotely using Zoom.

Evaluate your own health regularly. Do not attend class or other on-campus events if you are not feeling well. Seek appropriate medical attention for treatment of illness. A doctor's note concerning absences is not required.

You are expected to attend class meetings in person if you are well. You must wear a mask covering nose and mouth in the classroom and sit at least six feet from others.

If you are not well, you are expected to attend class meetings remotely via Zoom if you can. The General Policy Regarding Attendance in the Wofford College Student Handbook makes you responsible for catching up on any missed classes.

If necessary, we will move to a synchronous, blended or a synchronous, remote model. Under those models, class meetings will be held in perspon and/or using Zoom. You will be expected to be in each of those Zoom meetings.

Computer usage during class meetings

Bring a charged laptop to each class meeting if you can. We will often work in-class exercises using a laptop. However, I will expect your laptop to be closed unless I direct you to use it. Take notes on paper. Your open laptop is usually a distraction not only for you, but for other students near you.

If you are remote and using your laptop for a Zoom connection, try to get access to a second monitor. That will facilitate your being able to see what is being done via screen sharing and what you will do as part of an in-class exercise.

Office hours

I will make every effort to keep the office hours listed at the top of this syllabus. If I must cancel or move office hours, I will announce the change in Piazza.

You do not need to make an appointment to meet with me during office hours. Just drop in via Zoom. I am usually working in my office and you can meet with me there as long as we observe social distancing. I will look at your computer screen by either connecting your computer to my external monitor or by having you share your screen using Zoom.

I appreciate your contacting me during my office hours since it is time I have set aside and cannot easily use for another purpose. However, I realize that you might have conflicts. You are welcome to contact me to set up an appointment. If you do, list some times that you are available. Please do not ask me when I am available. Or you are welcome to drop by my office if you think I might be there.

Late work

You must meet project and paper deadlines. You may be able to submit a project late if both of these conditions are met:

  1. You contact me at least a day before the deadline to request an extension. In the request, include:
    1. a description of the problems you are facing
    2. how much more time you need
  2. You submit by the deadline the work you have completed so far even if you receive an extension.

Communication

Post questions and comments about this course on the Q&A page at Piazza. You are encouraged to respond to a question or to edit a response to a question. We are all learning together. If you send me a question via email or via private Piazza post that should be posted publicly at Piazza, my reply will direct you to post your question publicly.

Do not post working code at Piazza. Do not include in a response either “fixed” code or a detailed description of how to change code to get it to work. It is okay to post non-working code.

I usually respond to email messages sent Sunday through Thursday within 24 hours. I will usually respond within 48 hours to messages sent on a Friday or a Saturday. I usually respond much sooner to Piazza posts since I have the Piazza app on my phone and receive notifications. However, keep in mind that teaching is my job and not my whole life.

You can send me email messages for private matters, such as letting me know you will be absent or that you'd like to schedule a meeting. However, I prefer that you post a private message via Piazza.

Academic integrity

The Honor Code requires faculty, staff, and students to maintain a high standard of individual honor and integrity. Work represented as your own must be your own.

I encourage you to collaborate with others in the class—that is, help or get help from others. However, you may not write code for another student or provide code to copy. Doing any of these things is a violation Honor Code.

What is the distinction between collaboration and cheating?

Collaboration

  • You may discuss a project with another person.
  • You may work together to figure out how to attack a problem or develop an algorithm.
  • You may describe an issue you are having, such as a bug in your code, and get suggestions for resolving it.

Ultimately, you must implement a solution to the problem yourself.

Cheating
  • You are cheating when you copy code from someone else or when you allow someone to copy from you.
  • You are cheating if you let someone else edit your code—or if you edit their code.
  • You are cheating if you are working along with another and decide together what code to write.

For some projects, you might be allowed to work with other students in the class as a part of a team. In this case, you are allowed to share all your work with your teammates. However, you are expected to do all of the work together. One student should not work without the others present and contributing.

Don’t cheat because you are up against a deadline. Start each assignment as soon as it is given. If you run into a glitch:

  • Seek help from me, either by posting at Piazza or consulting with me.
  • Submit on time the work you have done, even if it is not fully completed. You will likely get partial credit for your work and/or an opportunity to fix any problems and raise the score.

Reasonable accommodations for students with disabilities

If you need accommodations, go to the Student tab in myWofford and investigate the Request Accommodations channel. I’ll make every effort to work with you. Take care of this during the first week of classes and before the first quiz.

We will delve at first into the C programming language. Then we will work through the Levitin book up through Chapter 10. Then we will circle back to study more deeply each strategy.

The schedule is subject to change.

Week Topics
JAN 04 Review of fundamental data structures.
C programming language.
JAN 11 C programming language.
Interview questions.
LeetCode.
JAN 18 Analysis framework: Big-O, Theta, Omega.
Analysis of nonrecursive algorithms.
JAN 25 Brute force algorithms.
Decrease and conquer algorithms.
Divide and conquer algorithms.
FEB 01 Analysis of nonrecursive algorithms.
LeetCode.
Writing a paper.
FEB 08 Transform and conquer algorithms.
Representation change.
FEB 15 Dynamic programming.
Greedy technique.
FEB 22 Graphs and b-trees.
MAR 01 Graph algorithms.
MAR 08 Algorithms + data structures.
C++ classes
MAR 15 Problem solving.
C++ inheritance
MAR 22 Problem solving.
C++ templates and overloading
MAR 29 Wrap-up.
APR 05 Final exam week
Presentations will be given on Monday, April 5 from 2:00-5:00 P.M.