Cs 312 Syllabus

CS 312: Algorithm Analysis Syllabus, Fall 2008 Section Information CS 312 Section 001 CS 312 Section 002 HONRS 345R Section 001

8:00-9:15 am, TTH 120 TMCB 9:30-10:45 am, TTH 120 TMCB 9:30-10:45 am, TTH 120 TMCB

Staff Listing Sean Warnick, Instructor Contact Information: [email protected], 422-6463, 2222 TMCB Office Hours: TTH 1-2pm or by appointment Tanja Brown, Teaching Assistant Contact Information: [email protected], Office Hours: To be announced Blake Durtschi, Teaching Assistant Contact Information: [email protected], Office Hours: To be announced

Texts and Resources The textbook for the course will be Algorithms by Dasgupta, Papadimitriou, and Vazirani. An on-line draft is currently available at www.cs.berkeley.edu/~vazirani/algorithms.html. We will also draw on excerpts from other texts that will be made available on the course website on Blackboard.

Overview CS 312 is a course about problems and their solutions; it is a course about information and how it is organized to meet specific objectives. The material is very deep, and it can launch a career of learning about how to be an expert problem solver. This expertise begins with a precise and concrete understanding of what is meant by a problem, how to formulate it technically, and how to analyze the nature of a well-formulated problem (e.g.

does it have a solution, is the solution unique, can a solution be computed in a reasonable amount of time and with reasonable computational resources?). Likewise, such expertise also demands an equally precise and concrete understanding of what is meant by a solution to a well-formulated problem, and how to characterize and analyze a welldefined solution (e.g. what is the difference between an algorithmic and analytical solution, what is the nature of a computation device that can execute an algorithmic solution or compute an analytical solution, how is the correctness of the solution measured, how is the efficiency of the solution measured?) This course lays the foundation for answering such questions by exploring a rich set of examples and techniques, and by giving students the opportunity to design, analyze, and implement a number of concrete solutions to important problems. Because the career of an expert problem solver can follow a variety of paths, the set of examples and practice problems in CS 312 are intentionally chosen from a broad range of application areas. Students will be exposed to problems from Scientific Computing, Computer Science, Engineering, Data Communications, Medicine, Cryptography, Media and Entertainment, Computational Biology, Operations Research and Management, Business Intelligence, Finance, or other applications. Moreover, although the course will focus on algorithms designed to execute on discrete sequential machines, we will also discuss the implications of designing algorithms to execute on other types of computers, such as analog computers, parallel machines, quantum computers, biological systems, and even human organizations. In this way, students may appreciate the fundamental nature of the ideas and skills they are developing about information and its organization, about problems and their solutions. Moreover, by exposing students to a wide arena of applications of algorithm analysis and design, we hope that students may find areas of interest and inspiration where they can target their career objectives and subsequent educational preparation.

Introduction to the Honors Section of CS 312 Enrolling in the honors section of CS 312 allows a student to substitute a different, more independently designed activity for the out-of-class participation experiences requirement of the regular class. Any student, whether enrolled in BYU’s Honors Program or not, may enroll in the honors section of the course. These students meet with the regular section of CS 312 of their choice (Section 001 or Section 002) for lectures, and they complete all the regular assignments except the out-of-class participation requirements. Instead of the regular out-of-class participation exercises, students in the honors section each design their own “response” to a “great idea” from computer science. This response will include a historical context, critical analysis, and a personal response. Note that these responses can be very creative, including, for example, application development, independent research, etc. or they may be a very simple, but thoughtful, written response (see https://honors.byu.edu:443/Main/files/GreatWorksResponseGuidelinesForm.pdf for more information). Moreover, honors students will have the opportunity to present their responses at the end of the semester and, for those who decide to pursue honors graduation, they may include their responses in their great works portfolio.

Sources for “Great Ideas” from computer science include (but are not limited to): 1. Any one of the topics from The New Turing Omnibus, by A.K. Dewdney 2. “Richard Bellman on the Birth of Dynamic Programming”, Stuart Dreyfus 3. Extractions from the Theory of Games and Economic Behavior, Von Neumann and Morgenstern, 4. Chaos: Making a New Science, by James Gleick 5. Classics from http://www.cs.berkeley.edu/~christos/classics/cs298.html 6. Any one of the five units from Information Science, by David Luenberger a. Entropy: The measure of information b. Economics: The value of information c. Encryption: The securing of information d. Extraction: The manipulation of information e. Emission: The transmission of information 7. Other ideas—propose something! Honors section students propose their extended participation experience early in the semester and, upon approval from the course instructor, work all semester in their project. Once a month there is an optional “Honors Lunch” planned where honors students and the instructor may discuss the progress of their projects over lunch. Grades between the regular and honors sections are determined in exactly the same way, except that the honors response and presentation are graded and substituted for the out-of-class participation experiences of the regular sections.

Expected Learning Outcomes I. Foundational Knowledge 1. Problems and Solutions: Understand what is meant by a technical problem formulation and the difference between an analytical vs. an algorithmic solution to a problem. a. Models: Appreciate the role of mathematics as a way of efficiently describing and reasoning about a problem or a solution concept. b. Analysis: Appreciate the nature of analysis, or mathematical reasoning about models of algorithms, models of computing machines, and possibly models of the computing environment, in characterizing properties of solutions, especially correctness, stability, and efficiency. c. Synthesis: Appreciate the power and limitations of computation for implementing algorithmic solutions to problems, as well as various stages of synthesis—problem formulation, algorithm design, implementation on a specific computing machine, and verification or testing. 2. Analysis Tools: Develop fluency with three analysis tools and understand how other analytic disciplines such as mathematics, probability, and statistics interrelate. a. Asymptotic Notation: Understand the process of modeling the efficiency of an algorithm and classifications based on those models (P, NP, etc.)

b. Elementary Probability Theory: Understand definitions of sample space, probability measure, random variables, and expectation for use in average case analysis and the analysis of randomized algorithms. Especially note how assumptions about probability measure impact analysis results. c. Difference Equations: Know how to solve linear constant coefficient difference equations and understand their role in modeling recursive structures, characterizing amortization, describing numerical methods, and representing dynamic programs (why they are called dynamic…). 3. Synthesis Paradigms: Develop fluency with categories of algorithms that are unified by the way they process information, including greedy algorithms, divideand-conquer algorithms, randomized algorithms, dynamic programs, graph-search algorithms, and linear programs. This fluency includes a. Exposure to a broad array of specific applications of algorithm design such as Data Compression (Huffman Codes), Image Processing (Fast Fourier Transform, Intelligent Scissors), Security (Public Key Cryptography), Graphics (Monte Carlo Integration), Computational Biology (DNA Sequence Alignment, RNA Secondary Structure Estimation), Operations Research (Project Selection, Airline Scheduling, Inventory Management, Transportation Networks, Scheduling), Computational Economics and Finance (Matching, Clustering, Regression, Time Series Analysis, Portfolio Optimization), etc. b. Practice with implementation issues, such as choice of data structures and code constructs (e.g. recursive vs. iterative implementations), by programming a solution to a specific problem for each synthesis paradigm in the Microsoft Visual Studio programming environment. II. Application and Integration 1. Apply problem formulation, solution development and analysis skills outside the classroom. 2. Understand applications of algorithms to a variety of disciplines including those listed in objective I.3.a. 3. Understand connections between mathematics, statistics, and probability to algorithms and the ways we organize information and computation to solve well formulated problems. III. Human Dimension, Caring, and Learning to Learn 1. Learn more about which fields and applications of algorithm analysis and design the student finds inspiring, enjoyable, and important. 2. Begin (or continue) to develop the attitudes, desires, and skills necessary to be an independent learner and thinker. 3. Consider the moral and spiritual implications of ideas from this course.

Learning Activities Learning activities for this course begin with in-class activities including lecture, discussion, group and individual problem solving exercises, and exams. Out-of-class activities include reading assignments, homework problems, programming projects, and “out-of-class participation” experiences. An average student should budget 2+ hours outside of class for every hour in class to earn an average grade (6+ hours/week). Students are encouraged to work in groups to learn and master the material. However, each assignment should reflect the student’s own understanding of the material and be his or her own work. When working in groups, students should list their collaborators on their write-ups and properly reference all sources. Reading Assignments Reading assignments are listed on the course schedule, although they may be modified in class as the learning experience is tailored to each group of students. It is the student’s responsibility to read ahead and come to class prepared for the discussion that day. “Jumping off” points will also typically be highlighted as places where students can go to learn more about a particular topic and dig deeper into the material. Students are encouraged to come to class prepared to share insights they gleaned from their preparation and reading. Homework Problems Homework will frequently be assigned. These problems are collected from various sources to give students practice thinking about and using the ideas discussed in class. Homework is due at the beginning of class on the scheduled due date as listed in the schedule; late assignments will not be accepted without prior arrangements having been made. Programming Projects There are five programming projects this semester. Each project will be described in a handout that outlines the problem to be solved and offers some direction about the design of a solution. Each student is expected to complete the projects in C# using the Visual Studio environment. Grades are based on the completion of a working program and a brief report describing your solution and addressing any questions or analyses described in the project description. Note that, as with other assignments, students are encouraged to work in groups to learn the material and understand the concepts. Nevertheless, your code should be your own; if you can’t explain everything about it or if you copied code from a friend, then you are cheating. Also, note that all projects must be completed to pass the class.

Out-of-class Participation Experiences The content of this class, algorithmic analysis and synthesis, has been described as the backbone of Computer Science. In fact, it is the backbone of all of science and engineering; the ways we organize information to solve problems is the heart of the scientific endeavor. As a result, you will be given credit for connecting material from this class to other professional activities. These experiences are student selected “extra-mile” activities that tie course material with other educational pursuits and interests. This can include attending Computer Science or other appropriate professional colloquia, augmenting a project from another class to include an algorithm analysis or novel synthesis component using ideas from CS 312, participating in the student chapter of ACM or other professional organizations that enable you to teach about Computer Science and the role algorithms play in our world today (e.g. though high school or grade school outreach programs, etc.), watching a relevant documentary on themes related to algorithms and their history (e.g. Nova, Scientific American Frontiers, etc.), using your training to solve problems of personal interest (e.g. matching algorithms for various purposes, personal finance calculator, visiting teaching route assignment, etc.), pursuing extra reading on an algorithms topic of personal interest (e.g. classic papers in CS, famous algorithms such as Google’s page rank, etc.), etc. The idea behind these experiences is not to give you more to do. Instead, it is to recognize you for things that you are already doing (or should be doing), and encouraging you to bring your CS education to the table when you do them. You are given credit for these experiences by turning in simple (but professional) reports on your activities. You should briefly describe what you did and the connection to CS 312. There is no set length of the report, but use good technical writing technique; don’t ramble but include enough information to be complete. For example, a report on a CS Colloquium might be about a page in length and give a brief summary of the talk followed by a critical analysis section where the student may elaborate a personal critique or appraisal of the results that were presented. On the other hand, a report on an augmentation to another class project might be 5 pages in length and go into extensive detail about the extra effort made to conduct a theoretical and empirical analysis of the algorithmic efficiency of a particular procedure, or it may include a rigorous formulation of the problem followed by a proof of correctness of the chosen solution. Each student will be expected to turn in a total of 5 single-spaced pages reporting on their participation experiences. Writing quality and professionalism will affect the grade. Exams There will be two midterms and a final. The midterm exams will be proctored in the testing center, have a three hour time limit, and will be closed-book closed-notes. The final exam will be in-class according to the University Calendar. Students registered for the honors section of the course may take their final at either time and will present their final reports on Friday December 19th. The final exam will be comprehensive, and one page of hand-written notes will be allowed.

Recitation Frequently, a Friday recitation will be provided by the TA’s as outlined on the schedule. The exact location and times of the recitation will depend on the class and be announced. These meetings are optional and simply give the student additional exposure and practice with many of the ideas from the lecture, reading material, or homework exercises. Study Groups On the first day of class, every student will be assigned to a study group. This group can be an additional resource to master the material and excel in the class. Honors Lunch The First Friday of each month will be a “brown-bag” lunch for the students enrolled in the honors section. This is a time for the students to discuss their projects with both the instructor and with each other. This is also a great time to talk about post-graduation plans, graduate schools, career possibilities, etc. and get the perspectives of both ones peers and the instructor.

Course Policies There are a number of university and course policies that impact the learning experience in CS 312. We highlight some important ones below. Grades Grades will be weighted by the following distribution and scale: Final Exam Midterm #1 Midterm #2 5 Programming Projects Homework Participation Experiences

25% 15% 15% 25% 15% 5%

100-93 A 93-90 A90-87 B+ 87-83 B

83-80 80-77 77-73 73-70

BC+ C C-

70-67 67-63 63-60 60-

D+ D DE

We reserve the right to curve grades in your favor. The University policies on UW and I grades will be strictly followed. Early and Late Submissions There are no special policies related to turning in homework or programming projects early. Likewise, late assignments are generally not accepted without prior arrangements. Nevertheless, each student has 5 free late days (not including holidays or weekends) to use at their discretion anytime during the semester before the last day of classes.

Cooperation Students in CS 312 are encouraged to work together to learn concepts and master the material. Nevertheless, every student is expected to write their own code, do their own work, and write up their own reports. If you do happen to work closely with other students on a particular assignment, please be sure to list them as collaborators on your report. Likewise, if you find ideas and concepts from Google or another source that you integrate into your solutions, always remember to properly cite your sources. Honor and Academic Honesty The Honor Code includes a statement of standards regarding academic honesty. Academic honesty includes writing your own programs, properly citing sources in reports and doing your own work on tests. Examples of academic dishonesty include sharing code for projects with other students, turning in someone else’s writing as your own report and cheating on an exam. The first violation of academic honesty standards will result in your course grade being lowered one grade level and you will be required to either redo the work or receive a zero on the assignment. The second violation will result in failing the class. All violations of academic honesty are documented and reported to the Honor Code office. Harassment Harassment of any kind is inappropriate. Specifically, BYU’s policy against sexual harassment extends not only to employees of the university but to students as well. If you encounter sexual harassment, gender-based discrimination, or other inappropriate behavior, please talk to your professor, contact the Equal Employment Office at 422-5895 or 367-5689, or contact the Honor Code Office at 422-2847. Disabilities BYU is committed to providing reasonable accommodation to qualified persons with disabilities. If you have any disability that may adversely affect your success in this course, please contact the University Accessibility Center at 422-2767. Services deemed appropriate will be coordinated with the student and instructor by that office.