Swedish name: Algoritmisk problemlösning
This syllabus is valid: 2012-01-02 valid to 2012-01-08 (newer version of the syllabus exists)
Syllabus for courses starting after 2012-01-09
Syllabus for courses starting before 2012-01-08
Course code: 5DV130
Credit points: 7.5
Education level: Second cycle
Grading scale: TH teknisk betygsskala
Responsible department: Department of Computing Science
The course treats problem solving with algorithmic methods. It highlights the whole process of problem solving, which consists in - formalization of a concrete computational problem, - structured analysis of the problem, - choice of solution method, based on a toolbox of algorithmic methods and advanced data structures, - implementation of the solution in a suitable programming language, and - evaluation of the results. Typical algorithmic methods that can be treated during the course include dynamic programming, greedy algorithms, linear programming, parallelization, randomization, and approximation. Typical data structures that are treated include Fibonacci heaps, B-trees, binary decision diagrams, and hash tables.
After finishing the course, the student will be able to - define a suitable formalization of an informally described computational problem; - describe important algorithmic methods and advanced data structures and analyze these with respect to time and space complexity; - systematically analyze a formally defined computational problem and use the results of the analysis to choose suitable algorithmic methods and data structures for solving it; - present a problem, its formalization, and solution both orally and in writing.
Eligibility requirements are 60 ECTS credits in Computing Science or Mathematics, or at least 2 years of completed studies, in both cases including the courses Data Structures and Algorithms (5DV108, 5DV127 eller 5DV128) and Fundamentals of Computer Science (5DV037) or equivalent. Proficiency in English equivalent to Swedish upper secondary course English A (IELTS (Academic) with a minimum overall score of 5.5 and no individual score below 5.0. TOEFL PBT (Paper-based Test) with a minimum total score of 530 and a minimum TWE score of 4. TOEFL IBT (Internet-based Test) with a minimum total score of 72 and a minimum score of 17 on the Writing Section). Where the language of instruction is Swedish, applicants must prove proficiency in Swedish to the level required for basic eligibility for higher studies.
Course meetings are held continuously during the semesters with at least 15 occasions per term (normally once a week). Normally the course is given as a "flexcourse" during the whole academic year (i.e. you can start the course at any time during a year). The idea is that the student, if he/she wishes, should be able to finish a course within a term. Teaching is delivered through - Lectures on algorithmic techniques and advanced data structures and their analysis with respect to time and space complexity; - Seminars, where the course participants discuss problems, possible formalizations, and possible solutions; - Student presentation, where the results of the students individual work on selected problems are presented. A course meeting can consist in a mixture of the above-mentioned forms of teaching. Since the course is meant to strengthen the student interest for the area and encourage continued learning, the participant's curiosity and enthusiasm for discovery plays a decisive role in the choice of seminar topics. The students shall also demonstrate their skills by solving problems individually and by implementing their solutions.
To pass the course, the student must actively participate in at least 12 course meetings (ELO 1,2). Further, the student must give at least two oral presentations (ELO 2,4) at two different given exam possibilities (see also below). In connection with at least one of them, the student must also deliver a written report (ELO 3,4). During an academic year, there are a number (at least six) of scheduled exam possibilities. The student may choose by him/herself when to to the exam and is responsible by him/herself to participate in all examinations parts at least once during an academic year. If the student at the end of the course is not graded with at least "Pass", the student is given the grade "Fail". After finishing the course, the student is graded with one of the grades Fail (U), Pass (3), Pass with Credit (4) or Pass with Distinction (5). In order to pass the course completely, all mandatory parts must be passed. The final grade of the course is a combining assessment of the results that is made only after all mandatory parts have been passed. A student who has passed an examination may not be re-examined. For students who do not pass the regular examination, there is another examination opportunity. The teachers decide the exact form of this examination, after consulting with the concerned students. A student who has taken two tests for a course or segment of a course without passing has the right to have another examiner assigned, unless there exist special reasons (Chapter 6, section 22, Higher Education Ordinance). Requests for new examiners are made to the head of the Department of Computing Science. TRANSFER OF CREDITS In an exam, this course may not be included, in whole or in part, together with another course of similar content. If in doubt, consult the student counselors at the Department of Computing Science and / or the program director of your program. Transfer of credits is considered individually (see the University Code of Rules and regulations for transfer of credits). An application for transfer of credits is made on a special form and should be submitted to the Faculty of Science and Technology, Umeå University.
Sipser Michael
Introduction to the theory of computation
2. ed. : Boston, Mass. : Thomson Course Technology : 2006 : 437 s. :
ISBN: 0-619-21764-2 (int. ed.)
Mandatory
Search the University Library catalogue
Cormen Thomas H.
Introduction to algorithms
3. ed. : Cambridge, Mass. : MIT Press : cop 2009 : xix, 1292 s. :
ISBN: 9780262033848 (inb.)
Mandatory
Search the University Library catalogue
Algorithms
Johnsonbaugh Richard, Schaefer Marcus
International ed. : Upper Saddle River, N.J. : Pearson Education : cop. 2004 : xiii, 752 s. :
ISBN: 0-02-360692-4
Mandatory
Search the University Library catalogue
Sipser Michael
Introduction to the theory of computation
2. ed. : Boston, Mass. : Thomson Course Technology : 2006 : 437 s. :
ISBN: 0-619-21764-2 (int. ed.)
Mandatory
Search the University Library catalogue
Lämplig kurslitteratur beror på vilken frågeställning som studenten valt att arbeta med och bestäms därför individuellt vid kursstart.
Inst för datavetenskap :