Course syllabus
Spring 2023
Course syllabus, Spring 2023
Title
Algorithmic methods for search and storage
Swedish title
Algoritmiska metoder för sökning och lagring
Course code
DA295E
Credits
7.5 credits
Grading scale
UA / Excellent (A), Very Good (B), Good (C), Satisfactory (D), Pass (E) or Fail (U)
Language of instruction
English
Decision-making body
Faculty of Technology and Society
Syllabus valid from
2022-01-17
Syllabus approval date
2021-05-31
Level
Basic level
Entry requirements
Alternatives:
- DA292A or DA252A or DA304A, or:
- 7.5 ECTS in algorithms and data structures which includes prevalent algorithms and data structures for sorting and searching
- 7.5 ECTS in programming
- English B/English 6 or the equivalent.
Main field
Computer Science
Progression level
G1F / First cycle, has less than 60 credits in first-cycle course/s as entry requirementsProgression level in relation to degree requirements
Independent course.
Course objectives
The course lets the student advance his or her knowledge in algorithmic methodology. Previously acquired knowledge of sorting algorithms and search data structures is deepened through the study of methods for efficient searching and storing of sequential data strings, for example, text in natural or formal languages, or genetic and other biological data. The student learns to make use of, adapt, and implement of efficient methods for representing, structuring, searching, and compressing large amounts of data.
Course contents
- Representation of sequential data, such as text or DNA sequences
- Radix sorting methods
- Data structures for efficient string lookup, such as inverted file, trie, suffix tree, and suffix array
- Methods for lossless data compression such as Huffman code, Ziv–Lempel compression, and the Burrows-Wheeler transform
- Methods for string search, and pattern matching using regular expressions
- Inverted file indexes for search engine use
Learning outcomes
Knowledge and understanding
For a passing grade, the student should be able to:
- Account for important algorithms and data structures for sequential data, their use, and their properties with regards to efficiency
- Account for the operation of important lossless data compression methods
- Motivate and explain efficiency properties of algorithmic methods to process, search, and compress sequential data
Skills and abilities
For a passing grade, the student should be able to:
- Choose, and when necessary adapt, algorithmic methods to process, search and compress sequential data.
- Implement algorithms and data structures for efficient storage and search in large quantities of data
Evaluation abilities and approach
For a passing grade, the student should be able to:
- Faced with a problem specification in processing sequential data, analyze the problem and critically choose an appropriate algorithmic approach for its solution
- Reason about, and critically evaluate, design and implementation choices from performance and storage space requirement aspects.
Learning activities
Lectures, teacher-supervised time for exercises with and without computer work, individual studies, and group work.
Assessment
The course examination consists of a written exam (4 ECTS), and mandatory assignments (3.5 ECTS).
An A–E passing grade requires that all mandatory assignments are approved and that the written exam is graded at least E. The final grade on the course is the grade on the written exam.
Course literature
- Sedgewick; Robert, Wayne, Kevin: Algorithms, 4th ed., Addison Wesley 2011.
- Witten, Ian H, Moffat, Alistair, Bell, Timothy C: Managing gigabytes: compressing and indexing documents and images, 2nd ed., Morgan Kaufman 1999.
- Additional literature provided by the course responsible teacher.
Course evaluation
The University provides students who are taking or have completed a course with the opportunity to share their experiences of and opinions about the course in the form of a course evaluation that is arranged by the University. The University compiles the course evaluations and notifies the results and any decisions regarding actions brought about by the course evaluations. The results shall be kept available for the students. (HF 1:14).
Interim rules
When a course is no longer given, or the contents have been radically changed, the student has the right to re-take the examination, which will be given twice during a one year period, according to the syllabus which was valid at the time of registration.
Additional information
Development of the course DA295A with a mainly similar content. The course overlaps with about 50% with the course DA357A.
The syllabus is a translation of a Swedish source text.