DSC 707- Design and Analysis of Algorithm

Contact Information
  • Instructor:
  • Office:
  • E-Mail:
  • Phone:
  • Office Hours:
Course Description

This course provides an understanding of the application of software technologies that enables users to make better and faster decisions based on big data features. This course covers the broad introduction to The course covers main approaches to design and analysis of algorithms including important algorithms and data structures, and results in complexity and computability. The main contents are: review of algorithm analysis (search in ordered array, binary insertion sort, merge sort, worst-case and average-case time complexity, minimum complexity of sorting n elements for small n, 2-3 trees, asymptotic notation); divide and conquer algorithms (master theorem, integer multiplication, matrix multiplication, fast Fourier transform); graphs (breadth-first search, connected components, topological ordering, depth-first search, way from planar graphs to Robertson-Seymour theorem); dynamic programming (chain matrix multiplication, shortest paths, edit distance, sequence alignment, extensions of dynamic programming); greedy algorithms (binary heaps, Dijkstra's algorithm, minimum spanning tree, Huffman codes, matroids); randomized algorithms (selection, quick sort, global minimum cut, hushing); P and NP (Cook's theorem, examples of NP-complete problems); approximate algorithms for NP-hard problems or polynomial algorithms for subproblems of NP-hard problems (set cover, vertex cover, maximum independent set, 2-SAT); partial recursive functions (theorem of Post, Diophantine equations); computations and undecidable problems (existence of complex problems, undecidability of halting problem, theorem of Rice, semantic and syntactical properties of programs). Students will learn the principles and best practices for how to use big data in order to support fact-based decision-making. Emphasis will be given to applications in various data which has big data facilities.

Course Outcomes

Upon the completion of this course, the student will be able to:

  1. Define and model the data structure with algorithms; DSLO 1
  2. use mathematical models and make the algorithms solve for equilibrium. Also models will be used analyze the policies related to various research field. - DSLO: 2,3,4
  3. analyze and critically evaluate from oral written, and visual materials.- DSLO: 3,6,8
  4. have the ability to predict the effects of changes in any kind of policy related to investigated field. –DSLO: 3,7,9,11

The course outcomes are assessed by using a case study, quizzes, two mid-term exams and a comprehensive final exam.

DSC Learning Outcomes:

Upon successful completion of the program, students will be able to:

  1. be competent in using appropriate algorithms.
  2. define, formulate and analyze a complex data structure involving human, material, machinery, money, information, time energy elements and various others and design it under realistic constraints and conditions by using making algorithms.
  3. design and conduct experiments, gather data, analyze and interpret results for investigating complex data structure by using algorithms.
  4. be proficient in statistical analysis of data and data management and apply algorithm concepts and methods to solve problems in various field.
  5. use information technologies effectively with the knowledge of state-of-the art hardware, and software capabilities related to algorithm designs.
  6. communicate effectively, using information technology and oral and written skills to enhance decision making process through better communication.
  7. make ethical and legal decisions by considering cultural differences.
  8. work efficiently in interdisciplinary and multidisciplinary teams by collaborating effectively, in addition to an individual effective working ability.
  9. enhance critical thinking skill by integrating relevant information, decision-making techniques, and concepts through the interdisciplinary machine learning science area.
  10. recognize the importance of algorithm design for entrepreneurship, innovation sustainable development and various other fields.
  11. have knowledge of the global and social effects of algorithm design. science and proper modelling of the data in various field
Prerequisites

The core courses, DS 701 and 703, have to be passed in order to take this course.
Computer programming skills. Understanding of basic data structures and algorithms.
Knowledge of probability. Basic knowledge in discrete mathematics.

Required Text(s) and Materials
  1. lecture notes will be distirubuted
  2. Algorithm Design, by J. Kleinberg and E. Tardos, Addison-Wesley, 2005 (main textbook) 1.
  3. Introduction to Algorithms (3rd Edition), by T. Cormen, C. Leiserson, R. Rivest, and C. Stein, The MIT Press, 2009
  4. Algorithms, by S. Dasgupta, C. Papadimitriou, and U. Vazirani, McGraw-Hill, 2006.
  5. Theory of Recursive Functions and Effective Computability, by H. Rogers, McGraw-Hill, 19674.
  6. Computers and Intractability. A Guide to the Theory of NP-Completeness, by M.R. Garey and D.S.Johnson, W.H. Freeman and Company, 1979
Assessment Method(s) and Evaluation
Mid-Term Exams:

This is 40% of the final average: Two mid-term exams will be administered by means of the portal on the scheduled date. Each exam will be worth equal point (20% each). Each mid-term exam consists of multiple choice questions and short work problem. There will be 1.5 hours to complete it.

Final Exam:

This is 35% of the final average: A comprehensive final exam will be administered by means of the portal on the scheduled date. The comprehensive final exam consists of multiple choice questions and short work problem. You only have a two-hour to complete it.

REMARK:

Both midterm exams and final exam also have one bonus question for extra credit. Questions in the exams are designed to make sure that you understand the basic economics tools used in air transportation. The types of questions on the exams will be similar to those asked in the study questions and the class materials covered during the class period.Since the final exam is cumulative, the materials covered after the second midterm exam will be given more weight in the final exam.

Quizzes:

This is 10% of the final average: Students are required to complete 10 online quizzes throughout the course by means of the portal. The online quizzes are composed of ten multiple-choice questions with each quiz covering a separate chapter. The overall score becomes available to each student upon completion of his or her test. Quizzes can be done ahead of time, but it cannot be made up after the deadline of each particular quiz. There will be no make-up online quiz if you fail to complete it by the deadline.

Case Study:

This is 15% of the final average: These assignment is aimed to improve the understating of current issues. Every student will be responsible for handing a topic in Design and Analysis of Algorithm. The case studies will be assigned to the student by the second week of semester or the students have the option to determine their own topic which must be approved by the instructor. On an assigned day of the week, assigned student will upload the case study to the portal as a write-up. The write-up of the case study is due on the last day of class. Grades will be based upon instructor evaluation of your write-up. More details will be given during the course of the semester.

Policy on Make- ups: Make-up examinations will only be administered to students with excused absences. Excused absences include death in the immediate family, University sponsored trips or critical illness. Verification is required and permission to miss an examination must be secured PRIOR TO the scheduled examination time. If this condition is not met, a zero will be given for the missed exam.

Grading
Grading Scale
Grade Quality Points
A = Excellent 90 – 100%
B = Good 80 – 89%
C = Satisfactory 70 – 79%
D = Passing 60 – 69%
F = Failing below 60%
Incompletes- I

Incompletes (I) demonstrate that a student was doing sufficient work at the end of a semester period but, for reasons beyond the control of the student, was unable to complete all requirements of the course in the related semester. The grade I obliges student to complete all course requirements within a time period that is specified by the instructor. This time period can’t exceed one academic calendar year from the end of the semester in that the grade I is assigned. The students has to arrange with the course instructor in order to complete all course requirements in a specified time period. If all course requirements are not completed by the students in a specified time period, I is changed to the grade F, unless the instructor has assigned a different grade.

Withdrawals-W

Students may withdraw from courses following the drop and add period until mid-term by completing the withdrawal process on the portal. A grade of "W" will appear in the student's official records if the student has withdrawn according to the SFU’s Withdrawal Policy. (Please see the SFU’s Withdrawal Policy for details.)

Attendance Policy

Participation and consistent attendance is essential for acceptable performance in the course. The students are expected to be present each class period except when special hardships occur, e.g. illness.
Regulations for attendance of Suje Florida University will be applied for this class.

Academic Integrity

Academic integrity is the responsibility of all Suje Florida University faculty and students. Cheating and plagiarism are not tolerated and will result in a failing grade, if the student is found guilty of cheating. Students are responsible for knowing and abiding by the Academic Integrity Policy. All students are expected to do their own work and to uphold a high standard of academic ethics.

Course Expectations
  1. As a portal course, it requires extensive work be done by students using the Internet. You must familiarize yourself with your portal account. Supplemental materials, including lecture notes will be posted on portal.
  2. Students are expected to read assigned material(s) prior to lecture and participate in discussions and activities.
  3. Log on at least three times a week – on different days in order to completely weekly assignments, assessments, discussions and/or other weekly deliverables as directed by the instructor.
  4. Check your e-mail often.
  5. Communications with the instructor should be via portal or e-mail. Email is preferred.
  6. It is your responsibility to ensure you are registered throughout the course.
  7. Discussion must always be civil. Rudeness or disrespect of other students will not be tolerated. We will respect the thoughts and opinions and others, even when we do not agree or believe the other person is terribly misinformed.
  8. Changes may be necessary in the syllabus. Students will be informed of changes to the syllabus.
  9. Students are responsible for any new material or announcements missed due to the absence.
  10. Students will use e-mail to communicate with the instructor. Emails sent Monday through Friday will be answered within 24 hours. Emails sent Saturday– Sunday may not be answered until Monday. If your email is not written in a respectful manner, you should not expect a response.
Tentative Detailed Course Content and Recommended Readings
Week Topic Recommended Reading(s)
1 Search and Sorting Lecture notes are available
2 Eid Al-Adha break Lecture notes are available
3 Divide and Conquer Algorithms Lecture notes are available
4 Graphs, Project Proposal Lecture notes are available
5 Dynamic Programming Lecture notes are available
6 Dynamic Programming Lecture notes are available
7 Greedy Algorithms Lecture notes are available
8 Randomized Algorithms, Lecture notes are available
9 P and NP Lecture notes are available
10 Work with NP Hard Problems Lecture notes are available
11 Work with NP Hard Problems Lecture notes are available
12 Partial Recursive function. Lecture notes are available
13 Computations and Unsolvable Problems Lecture notes are available
14 Computations and Unsolvable Problems, Final Presentation of Project, Final Lecture notes are available
15 Computations and Unsolvable Problems, Final Presentation of Project, Final Lecture notes are available
16

FINAL EXAM

Student Opinion of Instruction

At the end of the term, all students will be expected to complete an online Student Opinion of Instruction survey that will be available on portal. Students will receive an email notification through their VSU email address when the SOI is available. SOI responses are anonymous to instructors/administrators. Instructors will be able to view only a summary of all responses two weeks after they have submitted final grades.

Title IX Statement

Suje Florida University is committed to creating a diverse and inclusive work and learning environment free from discrimination and harassment. Discrimination on the basis of race, color, ethnicity, national origin, sex (including pregnancy status, sexual harassment and sexual violence), sexual orientation, gender identity, religion, age, national origin, disability, genetic information, or veteran status, in the Suje Florida University's programs and activities is prohibited as required by applicable laws and regulations such as Title IX. The individual designated with responsibility for coordination of compliance efforts and receipt of inquiries concerning nondiscrimination policies is the University's Title IX Coordinator.

Access Statement

Students with disabilities who are experiencing barriers in this course may contact the Access Office for assistance in determining and implementing reasonable accommodations.