Algoritmlar va ma’lumot tuzilmalari nazariyasi

Algoritmlar haqida umumiy tushunchalar:

• Algoritm va algoritm murakkabligi
• Big O termini haqida
• Algoritmlarda Divide and Conquer texnikasi

Stack va Queue:

• Ma’lumot tuzilmalari (data structures), Linked List, Stack, Queue
• Arifmetik ifodani hisoblash. Dijkstra’ning ikki stack algoritmi

Union Find:

• Dinamik bog’lanish (Dynamic Connectivity), Union-Find

Tartiblash algoritmlari:

• Insertion sort
• Selection sort
• Shellsort
• Mergesort
• Quicksort
• Dijkstra’ning uch tomonlama bo’lish (3-way partitioning) algoritmi
• Heapsort. Binary Heap asosida tartiblash
• Topological sort
• Radix sort. Key indeksli sanoq bilan tartiblash
• LSD Radix sort
• MSD Radix sort
• 3-way Radix Quicksort

Aralashtirish (shuffle):

• Aralashtirish algoritmi. Array’ni aralashtirish (shuffle)

Quickselect:

• Array’dan k-nchi kichik elementni topish

Priority Queue:

• Priority queue. Ustuvor navbatlar ma’lumotlar to’plami

Tree:

• Tree ma’lumotlar tuzilmasi. Binary Tree
• Binary Heap ma’lumotlar to’plami
• Binary search tree
• Binary search tree ustida amallar. API yozish
• 2-3 tree
• Red-black tree
• Red-black tree ustida amallar. API yozish
• AVL-tree
• AVL-Tree ustida amallar. API yozish
• B-tree
• 1D range search. Binary search tree’dan berilgan oraliqdagi qiymatlarni topish
• 2D range search. KD-tree

Symbol table:

• Dictionary (yoki Symbol table)

Hashtable:

• Hash table va Javascriptda hash table’ni ifodalash
• Hash table’da collision’ni bartaraf qilish. Separate chaining va Linear probing

Graph:

• Graph ma’lumotlar tuzilmasi
• Graph’ni kodda ifodalash. Graph API
• Depth first search algoritmi
• Breadth first search algoritmi
• Graph’da bog’langan komponentlar
• Graph masalalari. Bipartite graph
• Graph’dagi aylanalarni topish
• Kenigsbergning yetti ko’prigi
• Directed graph’da kuchli bog’langan komponentlar
• Minimum spanning tree
• Greedy algoritmi
• Minimum spanning tree’ni topish uchun Kruskal algoritmi
• Minimum spanning tree’ni topish uchun Prim algoritmi
• Shortest path – digraph’da qisqa yo’llar haqida
• Shortest’ path’ni topish uchun Dijkstra algoritmi
• Weight’ga ega DAGlarda shortest path’ni topish
• Digraph’da negativ weight’lar
• Digraph’da minimum cut va maximum flow masalalari
• Maximum flow’ni topish uchun Ford-Fulkerson algoritmi
• Ford-Fulkerson algoritmini kodda ifodalash

Radix

• Radix sort. Key indeksli sanoq bilan tartiblash
• LSD Radix sort
• MSD Radix sort
• 3-way Radix Quicksort
• Suffix array va matnni suffix array’da qayta ishlash

Tries:

• R-way tries
• Ternary search tries
• Trie ma’lumot tuzilmasida string amallari

Matn ichida qidiruv:

• Brute-force yondashuvi
• Knuth-Morris-Pratt algoritmi
• Boyer-Moore algoritmi
• Rabin-Karp algoritmi

Regular expressions:

• Regular expressions
• Regular Expressions va Nondeterministic Finite Automaton
• NFA simulyatsiyasi va API

Dynamic programming:

• Dynamic programming
• Ryukzak masalasi (Knapsack problem)
• Minimum edit distance

Geometriyada dasturlash:

• Convex hull. Yuzani qamrab oluvchi eng kichik perimetrni topish
• 2D line segment intersection. Sweep line algoritmi
• 1D interval search. Intervallar kesishmasini topish
• 2D rectangle intersection search