thalg_notes.tex

% Geometry setup
\documentclass[a4paper]{article}
\usepackage[margin=1.5cm]{geometry}

% Language setup
\usepackage[T1]{fontenc} % Output character encoding
\usepackage[utf8]{inputenc} % Input character encoding

% Spacing setup
\setlength{\parindent}{0pt} % No paragraph indenting
\setlength{\parskip}{5pt} % Set spacing between paragraphs
\frenchspacing
\newcommand{\rmspace}{\vspace{-19pt}}

% Dependency setup
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{mathtools}
\usepackage{dsfont}
\usepackage{listings}
\usepackage{float}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{url}
\usepackage[comma,authoryear]{natbib}
\usepackage[shortlabels]{enumitem}
\usepackage{minted}
\usepackage{makecell}
\usepackage{stmaryrd}

\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}

% Code pretty print
\usepackage{minted}

% Hyperlink format
\usepackage{xcolor}
\hypersetup{
    colorlinks,
    linkcolor={red!50!black},
    citecolor={blue!50!black},
    urlcolor={blue!80!black}
}

% Title setup
\author{Viktória Nemkin (nemkin@cs.bme.hu)}
\title{Practice Session Notes: Theory of Algorithms}

% Custom commands
\newcommand{\lineparagraph}[1]{\paragraph{#1}\mbox{}\\}
\newcommand{\titlemath}[1]{\texorpdfstring{#1}{Lg}}
\newcommand{\separate}{\vspace{2mm}\hrulefill{}\vspace{2mm}}
\newcommand{\condition}{\text{, }~}

% Supress warnings
\hbadness=99999 % Underfull hbox

% Document
\begin{document}
\maketitle

These, are my practice session notes, they are based on my personal notes and on the Hungarian course's solutions, found here under the heading \textbf{''A gyakorlatokon használt feladatsorok''}:\\ \url{http://www.cs.bme.hu/~csima/algel2020/index_2020_tavasz_vegleges.html} $\rightarrow$ In the case of hashings, this guide uses open hashings with quadratic probing by starting from the left, while we start that one to the right. Check Session 13, Exercise 9 for details!

This is a work in progress, I am updating these whenever I have time.

\textbf{Mistakes are possible}, if you spot any or if you have any questions about these notes, please contact me at nemkin@cs.bme.hu or in MS Teams.

\textbf{Version log}: \href{https://github.com/nemkin/thalg-notes/commits/main}{https://github.com/nemkin/thalg-notes/commits/main} - So you can check what was updated and when. (Or send me a PR if you find any errors? :) )

\tableofcontents
\pagebreak

\section{February 16th (Session 1): O, \titlemath{$\Omega$, $\Theta$}, pattern matching}
\input{01/01}\pagebreak
\input{01/02}\pagebreak
\input{01/03}\pagebreak
\input{01/04}\pagebreak
\input{01/05}\pagebreak
\input{01/06}\pagebreak
\input{01/07}\pagebreak
\input{01/08}\pagebreak
\input{01/09}\pagebreak
\input{01/10}\pagebreak
\input{01/11}\pagebreak
\input{01/12}\pagebreak

\section{February 23rd (Session 2): Finite Automata}
\input{02/01}\pagebreak
\input{02/02}\pagebreak
\input{02/03}\pagebreak
\input{02/04}\pagebreak
\input{02/05}\pagebreak
\input{02/06}\pagebreak
\input{02/07}\pagebreak
\input{02/08}\pagebreak
\input{02/09}\pagebreak
\input{02/10}\pagebreak
\input{02/11}\pagebreak
\input{02/12}\pagebreak
\input{02/13}\pagebreak

\section{March 2nd (Session 3): Regular expressions, Context-free languages}
\input{03/01}\pagebreak
\input{03/02}\pagebreak
\input{03/03}\pagebreak
\input{03/04}\pagebreak
\input{03/05}\pagebreak
\input{03/06}\pagebreak
\input{03/07}\pagebreak
\input{03/08}\pagebreak
\input{03/09}\pagebreak
\input{03/10}\pagebreak
\input{03/11}\pagebreak
\input{03/12}\pagebreak

\section{March 9th (Session 4): Context-free grammars, Pushdown automata}
\input{04/01}\pagebreak
\input{04/02}\pagebreak
\input{04/03}\pagebreak
\input{04/04}\pagebreak
\input{04/05}\pagebreak
\input{04/06}\pagebreak
\input{04/07}\pagebreak
\input{04/08}\pagebreak
\input{04/09}\pagebreak
\input{04/10}\pagebreak
\input{04/11}\pagebreak
\input{04/12}\pagebreak

\section{March 23th (Session 5): Turing-machines}
\input{05/01}\pagebreak
\input{05/02}\pagebreak
\input{05/03}\pagebreak
\input{05/04}\pagebreak
\input{05/05}\pagebreak
\input{05/06}\pagebreak
\input{05/07}\pagebreak
\input{05/08}\pagebreak
\input{05/09}\pagebreak

\section{March 30th (Session 6): Turing-machines 2}
\input{06/01}\pagebreak
\input{06/02}\pagebreak
\input{06/03}\pagebreak
\input{06/04}\pagebreak
\input{06/05}\pagebreak
\input{06/06}\pagebreak
\input{06/07}\pagebreak
\input{06/08}\pagebreak

\section{April 6th (Session 7): P, NP}
\input{07/01}\pagebreak
\input{07/02}\pagebreak
\input{07/03}\pagebreak
\input{07/04}\pagebreak
\input{07/05}\pagebreak
\input{07/06}\pagebreak
\input{07/07}\pagebreak
\input{07/08}\pagebreak
\input{07/09}\pagebreak

\section{April 13th (Session 8): NP-completeness}
\input{08/karp}\pagebreak
\input{08/01}\pagebreak
\input{08/02}\pagebreak
\input{08/03}\pagebreak
\input{08/04}\pagebreak
\input{08/05}\pagebreak
\input{08/06}\pagebreak
\input{08/07}\pagebreak
\input{08/08}\pagebreak
\input{08/09}\pagebreak
\input{08/10}\pagebreak
\input{08/11}\pagebreak
\input{08/12}\pagebreak

\section{April 27th (Session 9): NP-completeness, Integer Programming, Linear Programming}
\input{09/01}\pagebreak
\input{09/02}\pagebreak
\input{09/03}\pagebreak
\input{09/04}\pagebreak
\input{09/05}\pagebreak
\input{09/06}\pagebreak
\input{09/07}\pagebreak
\input{09/08}\pagebreak
\input{09/09}\pagebreak
\input{09/10}\pagebreak

\section{May 5th (Session 10): Binpacking FF/FFD, Dynamic Programming}
\input{10/01}\pagebreak
\input{10/02}\pagebreak
\input{10/03}\pagebreak
\input{10/04}\pagebreak
\input{10/05}\pagebreak
\input{10/06}\pagebreak
\input{10/07}\pagebreak
\input{10/07}\pagebreak
\input{10/08}\pagebreak
\input{10/09}\pagebreak
\input{10/10}\pagebreak
\input{10/11}\pagebreak
\pagebreak

\section{May 11th (Session 11): Sorting, Binary Search Trees}
\input{11/01}\pagebreak
\input{11/02}\pagebreak
\input{11/03}\pagebreak
\input{11/04}\pagebreak
\input{11/05}\pagebreak
\input{11/06}\pagebreak
\input{11/07}\pagebreak
\input{11/08}\pagebreak
\input{11/09}\pagebreak
\input{11/10}\pagebreak
\input{11/11}\pagebreak
\input{11/12}\pagebreak
\input{11/13}\pagebreak
\input{11/14}\pagebreak
\input{11/15}\pagebreak

\section{May 18th (Session 12): Binary Search Trees, 2-3-trees, Hash}
\subsection{Solutions written by Prof. Attila Sali, on Moodle}
Solutions to May 18th (Session 12): Binary Search Trees, 2-3-trees, Hash: \href{https://edu.vik.bme.hu/pluginfile.php/325461/mod\_resource/content/1/main.pdf}{To Moodle}.
\pagebreak
\input{12/09}\pagebreak

\section{Exam: 2019. 01. 06.}
\input{exams/2019_01_06/01}\pagebreak

\section{Exam: 2019. 06. 17.}
\setcounter{subsection}{3}
\input{exams/2019_06_17/04}\pagebreak

\section{Exam: 2020. 01. 23.}
\setcounter{subsection}{2}
\input{exams/2020_01_23/03}\pagebreak

\section{Exam: 2022. 05. 30.}
\input{exams/2022_05_30/01}\pagebreak
\input{exams/2022_05_30/02}\pagebreak
\input{exams/2022_05_30/03}\pagebreak
\input{exams/2022_05_30/04}\pagebreak
\input{exams/2022_05_30/05}\pagebreak
\input{exams/2022_05_30/06}\pagebreak
\input{exams/2022_05_30/07}\pagebreak

\section{Exam: 2022. 06. 13.}
\input{exams/2022_06_13/01}\pagebreak
\input{exams/2022_06_13/02}\pagebreak
\input{exams/2022_06_13/03}\pagebreak
\input{exams/2022_06_13/04}\pagebreak
\input{exams/2022_06_13/05}\pagebreak
\input{exams/2022_06_13/06}\pagebreak

\section{Exam: 2022. 06. 20.}
\input{exams/2022_06_20/01}\pagebreak
\input{exams/2022_06_20/02}\pagebreak
\input{exams/2022_06_20/03}\pagebreak
\input{exams/2022_06_20/04}\pagebreak
\input{exams/2022_06_20/05}\pagebreak
\input{exams/2022_06_20/06}\pagebreak
\input{exams/2022_06_20/07}\pagebreak

\end{document}