BIG-O ORANGE: ADVANCED ALGORITHMS

(THUẬT TOÁN NÂNG CAO)

Bạn muốn học lập trình Thuật Toán  nâng cao để tham gia các vòng phỏng vấn các công ty công nghệ lớn Google, Facebook, Amazon, Apple… Bạn muốn tìm kiếm một cơ hội thực tập hoặc làm việc toàn thời gian cho các công ty đòi hỏi đầu vào là kiến thức Thuật Toán. Bạn muốn xây dựng đội ngủ làm việc với những Thuật Toán cao cấp để tối ưu hóa sản phẩm của mình.

Khóa học Big-O Orange: Advanced Algorithms (Thuật Toán nâng cao) sẽ phù hợp với bạn, giúp bạn nâng cao kỹ thuật lập trình Thuật Toán với các kiến thức về Toán học, Quy hoạch động, Cây phân đoạn. Giải quyết các bài toán trên các trang lập trình Thuật Toán nổi tiếng Leetcode, Interviewbit, Topcoder. Ngôn ngữ lập trình minh họa khóa học C++, Python, Java.

Học phí khóa học: Ưu đãi đặc biệt 5 bạn đăng ký sớm giảm học phí 1.000.000 VNĐ. Chi tiết xem link đăng ký học đính kèm bên dưới.

Ưu tiên giảm thêm học viên đã học tại Big-O khóa Green và Blue. Ngoài ra chúng tôi có chương trình hổ trợ đóng học phí nhiều lần cho các bạn Học Sinh, Sinh Viên các bạn vui lòng liên hệ qua Email: admin@bigocoding.com để được hỗ trợ.

Bạn có thể xem thời gian khai giảng, lịch học cụ thể và đăng ký tại đây

ĐỐI TƯỢNG HỌC PHÙ HỢP

  • Tiên quyết: Học viên đã học qua lớp học Blue tại Big-O, nếu chưa học qua lớp Blue cần làm bài kiểm tra đầu vào để xác định có phù hợp lớp này hay không.

  • Tùy chọn: Đã học xong và nắm vững 3 môn học Cấu Trúc Dữ Liệu & Thuật Toán Cơ Bản, Cấu Trúc Dữ Liệu & Thuật Toán Nâng Cao, Lý Thuyết Đồ Thị.

  • Nếu bạn chưa xác định được mình phù hợp của lớp học Big-O Orange này vui lòng gọi cho chúng tôi qua số điện thoại: 0937.401.483 để được tư vấn học các lớp học phù hợp với trình độ của bạn. Hoặc chát nhanh với chúng tôi qua Mesenger Facebook tại m.me/BigOCoding

BÀI TẬP MINH HỌA KHÓA HỌC

  • Bài tập 100% bằng Tiếng Anh (được hướng dẫn chi tiết lại bằng Tiếng Việt).
  • Trích từ những câu hỏi phỏng vấn tuyển dụng Intern hoặc Fulltime của: Google, Facebook, Amazon, Microsoft…
  • Trích từ các chức năng thực tế của các dự án của các công ty.
  • Trích từ những kỳ thi nổi tiếng như ACM-ICPC, Olympic Tin Học (dạng câu đơn giản).

THỜI GIAN VÀ ĐỊA ĐIỂM HỌC

  • Thời gian: 2 tháng (8 tuần)
  • Hình thức học: Offline và online.
  • Học offline tại: Tòa Nhà Jabes 1, Số 244 Cống Quỳnh, phường Phạm Ngũ Lão, Quận 1, Hồ Chí Minh.
  • Học online qua: Zoom.
  • Số lượng học viên mỗi lớp: Tối đa 25  đến 30 học viên.
  • Mỗi lớp có 1 Giảng Viên chính và 5 trợ giảng.
  • Đặc biệt có giờ Office Hours (giờ học phụ đạo) hàng tuần cho học viên ôn lại bài học nếu không theo kịp tiến độ bài học.

SỰ KHÁC BIỆT CỦA CÁC KHÓA HỌC TẠI BIG-O CODING

1. CHƯƠNG TRÌNH GIẢNG DẠY:

  • Được giảng dạy bởi chuyên gia về Thuật Toán với nhiều năm kinh nghiệm (xem thêm phần “đội ngũ giảng dạy“).
  • Làm việc trên các hệ thống chấm bài nổi tiếng trên thế giới Codeforces, Hackerrank, Hackerearth, SPOJ…
  • Được gặp gỡ và trao đổi với những bạn thành công đi trước chia sẻ kinh nghiệm học tập Thuật Toán và kinh nghiệm làm việc.
  • Mỗi lớp học ngoài Giảng Viên chính đều có 5 trợ giảng: Trợ giảng phụ trách tại lớp và trợ giảng phụ trách diễn đàn riêng của lớp đảm bảo mọi thắc mắc của học viên sẽ được trả lời nhanh chóng mọi lúc mọi nơi.

2. MỤC TIÊU ĐẠT ĐƯỢC SAU KHÓA HỌC:

  • Tự xây dựng thuật toán để giải quyết riêng từng vấn đề gặp phải.
  • Nếu bạn là Software Engineer bạn có thể tham dự các kỳ thi thuật toán của các công ty công nghệ Samsung Challenge, Facebook Hacker Cup (Round 2), Google Codejam (Round 2).
  • Nếu bạn là Học Sinh, Sinh viên bạn có thể tham dự các kỳ thi Olympic Tin, IOI (International Olympiad in Informatics), ACM-ICPC, Codeforces (Div 1).
  • Có thể ứng dụng và xây dựng Thuật Toán vào dự án thực tế.
  • Chuẩn bị kiến thức để đạt mục tiêu xa hơn là Internship, Fulltime các công ty công nghệ hàng đầu.

ĐỀ CƯƠNG CHI  TIẾT KHÓA HỌC

Tìm hiểu thuật toán đồ thị nâng cao - Topological sort ứng dụng trong sắp xếp các công việc/khóa học đảm bảo tính tuần tự, trong lĩnh vực Blockchain,… Giới thiệu hai thuật toán tìm thứ tự Topo: thuật toán dựa trên ý tưởng DFS và thuật toán Kahn dựa trên ý tưởng BFS.

Các bài tập ứng dụng:

  • Tìm số khóa học ít nhất cần đăng ký và thứ tự học các khóa đó.
  • Tìm thứ tự bảng chữ cái phù hợp để đảm bảo chuỗi những tên cho trước theo “thứ tự bảng chữ cái”.

    • Giới thiệu các thao tác trên bit từ cơ bản đến nâng cao. Các thao tác này giúp tối ưu tối đa thời gian chạy của chương trình nên được ứng dụng phần lớn trong các hệ thống nhúng, mạng máy tính và xử lý hình ảnh.

    Giải quyết các bài toán:

  • Tìm XOR của tất cả các phần tử trong một đoạn của mảng.
  • Giúp Samu lên thực đơn cho bữa tiệc đảm bảo mỗi người tham dự đều tìm thấy ít nhất một món ăn yêu thích.

    • Tìm hiểu thuật toán quay lui (backtracking) qua hai bài toán kinh điển: N-queen và tìm tất cả các hoán vị của một chuỗi.

    Giải quyết các bài toán thực tế:

  • Tìm cơ hội chiến thắng trong trò chơi Lotto của Đức.
  • Giải bài toán tìm từ trong trò chơi Boggle.

    • Tìm hiểu phương pháp chia để trị (divide and conquer) mang ý tưởng đệ quy được ứng dụng rộng rãi trong các thuật toán kinh điển như binary search, quicksort, merge sort,… Minh họa qua hai bài toán: tìm cặp điểm gần nhất trong mặt phẳng (closest Pair of Points), tìm mảng con có tổng lớn nhất (maximum subarray sum).

    Giải quyết một số bài toán thực tế:

  • Tìm khoảng cách giữa hai điểm gần nhất trong mặt phẳng.
  • Bài toán sơn hàng rào sao cho tiết kiệm sơn nhất
  • Tìm những cặp đỉnh có khoảng cách cho trước trong cây (áp dụng kỹ thuật Centroid Decomposition).

    • Giới thiệu giải thuật Greedy – một phương pháp phổ biến trong thiết kế các thuật toán như Dijkstra, Kruskal, Huffman Coding… Giải thuật này có hiệu quả về mặt thời gian nhưng không đảm bảo tính chính xác. Giải quyết bài toán tô màu đồ thị (graph coloring) và bài toán phân bố taxi.

    Giải quyết một số bài toán:

  • Xây dựng các cuộc giao dịch mua rượu tối ưu về mặt vận chuyển.
  • Tính số bước tối thiểu để xây dựng một chuỗi hoán vị mới bằng cách tăng giảm các số trong chuỗi ban đầu.

    • Làm quen với lý thuyết số (number theory). Tìm hiểu những tính chất, định lý liên quan đến phép chia lấy dư (modulo operation): định lý Fermat nhỏ, thuật toán Euclid,…

    Các bài tập ứng dụng:

  • Bài toán chia kẹo Euler (tính tổ hợp).
  • Tính số kẹo còn dư sau khi chia đều cho bạn bè.

    • Tìm hiểu hai thuật toán liên quan đến số nguyên tố: sàn nguyên tố Eratosthenes (sieve of Eratosthenes) áp dụng để tìm tất cả số nguyên tố nhỏ hơn N và thuật toán tìm hàm phi Euler (Euler’s totient function) của một số.

    Bài tập ứng dụng:

  • Bài toán tìm ước số nguyên tố lớn nhất của một số.
  • Tìm các số nguyên tố thuộc khoảng giữa trong đoạn [1, N].
  • Tìm số nguyên tố đảo ngữ (anagrammatic prime).

    • Kỳ thi giữa kỳ của khóa học.

    Tìm hiểu cấu trúc dữ liệu quan trọng có ứng dụng rộng rãi: bảng băm (hash table). Xây dựng các hàm băm cơ bản đến nâng cao: hàm băm Robert Sedgewick, polynomial, cyclic shift,… Phân tích các phương pháp giải quyết đụng độ: separate chaining, open addressing,… Giới thiệu bài toán Least Recently Used Cache (LRU Cache).

    Bài tập ứng dụng:

  • Tìm quy luật đường đi của nhà vua trên bàn cờ.
  • Tìm hậu tố của chuỗi trong làng Noapara.

    • Làm quen với khái niệm quy hoạch động (dynamic programming), so sánh hai phương pháp Top-Down và Bottom-Up. Tìm hiểu hai bài toán quy hoạch động kinh điển: bài toán leo cầu thang (staircase problem) và bài toán đổi tiền (coin change problem).

    Giải quyết các bài toán:

  • Tìm số cách thanh toán hóa đơn sử dụng những tờ tiền với mệnh giá cho trước.
  • Tính số cách giải mã một chuỗi mật mã.

    • Tìm hiểu công thức quy hoạch động cho bài toán tìm kiếm dãy con chung dài nhất của hai dãy cho trước (longest common subsequence). Giới thiệu bài toán Diff – xây dựng công cụ so sánh các dòng code của hai mã nguồn.

    Giải quyết bài toán:

  • Tìm điểm chung giữa hai văn bản đề xuất.
  • Tìm LCS của ba chuỗi.

    • Làm quen với một bài toán kinh điển khác của quy hoạch động – bài toán tìm dãy con tăng dài nhất. Giới thiệu phương pháp cải tiến LIS bằng Binary search với độ phức tạp O(NlogN). Tìm hiểu về ứng dụng của LIS trong những thuật toán Diff sử dụng trong các hệ thống quản lý phiên bản (version control system) như Git.

    Bài toán vận dụng:

  • Xây dựng tháp Babylon cao nhất có thể từ những khối đá hình chữ nhật.

    • Tìm hiểu 3 loại bài toán balo (Knapsack problem) thường gặp:

    Giải quyết một số bài toán:

  • 0/1 Knapsack problem
  • Multiple Knapsack problem
  • Fractional Knapsack problem

    • Giới thiệu thuật toán Knutt-Morris-Pratt áp dụng trong bài toán tìm kiếm vị trí xuất hiện của chuỗi mẫu P (pattern) trong một chuỗi văn bản T (text) (string matching problem) với thời gian chạy tuyến tính. Hiểu cách xây dựng mảng prefix trong giai đoạn tiền xử lý của thuật toán và áp dụng vào những vấn đề liên quan. Những ứng dụng liên quan: giải trình tự DNA, phân loại mail rác,…

    Giải quyết các bài toán:

  • Đếm số lần xuất hiện của một chuỗi trong một chuỗi khác.
  • Tìm “căn bậc N” của một chuỗi ký tự.

    • Tìm hiểu cấu trúc dữ liệu Segment Tree (cây phân đoạn). Giải quyết bài toán tính tổng một đoạn bất kỳ trên dãy số bằng cây phân đoạn. Sử dụng kỹ thuật Lazy Propagation để tối ưu việc cập nhật giá trị (update) trên một đoạn của cây phân đoạn.

    Giải quyết các bài toán liên quan đến cập nhật và truy vấn trên dãy số.

    Kỳ thi cuối kỳ.