We may earn an affiliate commission when you visit our partners.
Course image
Wanling Qu

课程教学目标

针对实际问题需求,进行数学建模并选择高效求解算法的训练,为提高学生的素质和创新能力打下必要的基础。主要内容涉及:面对实际问题建立数学模型、设计正确的求解算法、算法的效率估计、改进算法的途径、问题计算复杂度的估计、难解问题的确定和应对策略等等。本课程是算法课程的基础部分,主要涉及算法的设计、分析与改进途径,其他有关计算复杂性的内容将在后续课程中加以介绍。

课程内容安排

Read more

课程教学目标

针对实际问题需求,进行数学建模并选择高效求解算法的训练,为提高学生的素质和创新能力打下必要的基础。主要内容涉及:面对实际问题建立数学模型、设计正确的求解算法、算法的效率估计、改进算法的途径、问题计算复杂度的估计、难解问题的确定和应对策略等等。本课程是算法课程的基础部分,主要涉及算法的设计、分析与改进途径,其他有关计算复杂性的内容将在后续课程中加以介绍。

课程内容安排

本课程的内容分成两大部分:算法的基础知识、通用算法设计技术与分析方法。

第一部分是算法基础知识,约占20%,主要介绍算法相关的基本概念和数学基础。比如,什么是算法的伪码描述?什么是算法最坏情况下和平均情况下的时间复杂度?算法时间复杂度函数的主要性质,算法复杂度估计中常用的数学方法,如序列求和及递推方程求解。

第二部分是通用的算法设计技术与分析方法,主要介绍分治策略、动态规划、贪心法、回溯与分支限界。主要介绍这些设计技术的使用条件、分析方法、改进途径,并给出一些重要的应用。

Enroll now

What's inside

Syllabus

算法基础
先通过几个典型的例子阐述算法设计与分析课程的学习内容及重要意义,接着介绍与算法有关的基本概念,如算法的伪码描述、时间复杂度函数的表示方法和一些常用的时间复杂度函数。
序列求和与递推方程
介绍在算法分析中所需要的一些数学基础知识,如与程序迭代有关的序列求和公式,在估计递归计算工作量时常用的递推方程及其求解方法等。
Read more
分治算法的设计与分析
分而治之是一种常用的算法设计技术。主要思想是将原始问题分解成若干个规模较小的独立的子问题,接着分别求解每个子问题,最后再将子问题的解综合以得到原始问题的解。通过本周的学习,你将了解分治算法的使用条件、主要的设计步骤、递归的实现技术、时间复杂度的分析方法、提高算法效率的途径等重要问题。
分治算法的典型应用
在对分治算法有了基本的认识以后,进一步介绍一些典型的分治算法的成功案例,包括各种选择算法、涉及信号降噪处理的卷积计算与快速傅立叶变换、涉及图形学的平面点集凸包的计算等。
动态规划算法
动态规划是另一种常用的算法设计技术。首先通过矩阵相乘的例子介绍动态规划算法的设计思想、主要步骤、分析方法、迭代实现与存储表示等。然后通过投资、背包、最长公共子序列等典型问题展现不同的动态规划算法在子问题划分与迭代计算时的特点和提高算法效率的技巧。
动态规划算法的典型应用
在对动态规划算法有了基本认识之后,进一步介绍运用动态规划算法的一些成功案例,如用于黑白图片存储的变位压缩算法、最大子段和的计算、最优二分检索树的构造以及生物信息学中的RNA二级结构预测和序列比对算法等。
贪心法的设计
贪心法是处理组合优化问题的常用算法。通过几个典型例子说明了贪心法的设计思想,同时重点阐述了贪心策略正确性的证明方法。针对某些不能保证对所有的输入都得到最优解的贪心策略讨论了其适用范围。
贪心算法的典型应用
给出了贪心法应用的一些成功案例,如与最优前缀码设计有关的哈夫曼算法、应用广泛的最小生成树Prim算法和Kruskal算法、在网络路由中寻找单源最短路径的Dijkstra算法等。
回溯算法的设计思想
回溯算法是一种基本的搜索技术,通过n后放置、0-1背包、货郎旅行、图的着色等问题介绍了回溯算法的设计思想、适用条件和实现方法,并给出了估计算法运行时间的一种抽样方法。
回溯算法的典型应用
介绍提升回溯算法搜索效率的分支限界技术,给出求解最大团、货郎、圆排列、邮票设计等回溯算法的典型应用实例。
期末考试

Good to know

Know what's good
, what to watch for
, and possible dealbreakers
An entry-level course for computer science learners who plan to continue their studies in computer science, software engineering, or data science
Content is broken down into real-world applicable skills like management, analysis, optimization and search techniques

Save this course

Save 算法设计与分析 Design and Analysis of Algorithms to your list so you can find it easily later:
Save

Reviews summary

Highly recommended algorithms course

This course is highly recommended by students, who describe it as the best algorithms course they have taken. The instructor is praised for their teaching skills and the course content is said to be well-structured and engaging. Students report that they learned a lot and would highly recommend this course to others.
屈老师非常棒!
"最好的算法课了,屈老师非常棒!"

Activities

Be better prepared before your course. Deepen your understanding during and after it. Supplement your coursework and achieve mastery of the topics covered in 算法设计与分析 Design and Analysis of Algorithms with these activities:
Read 'Algorithm Design Manual' by Steven Skiena
Reinforce your understanding of algorithm design principles and techniques through a comprehensive book
Show steps
  • Obtain a copy of the book, either physically or digitally
  • Set aside dedicated time for reading and studying the book
  • Take notes, highlight important concepts, and work through the examples provided
  • Apply the techniques learned in the book to your own projects and assignments
Form a study group with classmates to discuss algorithms and solve problems together
Enhance your understanding and collaboration skills by forming a study group with classmates
Show steps
  • Identify classmates who are interested in forming a study group
  • Determine a regular meeting schedule and location
  • Prepare for each session by reviewing the assigned material and identifying topics for discussion
  • Actively participate in discussions, ask questions, and share your insights
  • Work together on solving problems and assignments
Attend a workshop on algorithm analysis and design
Gain practical insights and learn from experts by attending a workshop on algorithm analysis and design
Show steps
  • Research and find workshops that align with your learning goals
  • Register for the workshop and make necessary arrangements
  • Attend the workshop actively, taking notes and engaging in discussions
  • Apply the knowledge and techniques learned in the workshop to your own projects
Four other activities
Expand to see all activities and additional details
Show all seven activities
Follow tutorials for algorithm analysis techniques
Enhance your understanding of algorithm analysis techniques through guided tutorials, solidifying your knowledge
Show steps
  • Identify reputable sources for tutorials, such as Coursera, edX, or YouTube channels like Khan Academy
  • Review the course syllabus and identify specific topics you need to strengthen
  • Find tutorials that align with those topics and start working through them
  • Take notes and actively engage with the material, pausing to reflect and practice
  • Complete the exercises and assignments associated with the tutorials
Solve algorithm problems on platforms like LeetCode or HackerRank
Refine your problem-solving and coding skills by practicing algorithm problems on online platforms
Show steps
  • Create an account on a platform like LeetCode or HackerRank
  • Start with easier problems and gradually increase the difficulty as you progress
  • Analyze the problem statements carefully and identify the key concepts and techniques involved
  • Develop and implement efficient algorithms to solve the problems
  • Review your solutions and identify areas for improvement
Develop an algorithm for a specific problem
Strengthen your problem-solving skills and understanding of algorithm design by creating an algorithm for a real-world problem
Show steps
  • Identify a problem that can be solved using an algorithm, such as finding the shortest path in a graph or sorting a list of numbers
  • Research different algorithm design techniques and select the most appropriate one
  • Implement the algorithm in a programming language of your choice, ensuring efficiency and accuracy
  • Test the algorithm thoroughly using a variety of inputs to ensure its correctness and performance
  • Document your algorithm and its implementation, including a detailed explanation of your approach and any challenges you faced
Create a blog or vlog to share your learnings and insights on algorithms
Solidify your understanding by teaching others, improve your communication skills, and contribute to the community
Show steps
  • Identify the topics you want to cover, focusing on areas where you have strong knowledge
  • Choose a platform for your blog or vlog, such as WordPress, Medium, or YouTube
  • Create high-quality content that is informative, engaging, and accessible to your target audience
  • Promote your blog or vlog through social media and other channels
  • Interact with your audience, respond to comments, and continue to grow your knowledge base

Career center

Learners who complete 算法设计与分析 Design and Analysis of Algorithms will develop knowledge and skills that may be useful to these careers:
Machine Learning Engineer
Machine Learning Engineers design, develop, and maintain machine learning models. This course provides a solid foundation in algorithm design, optimization techniques, and computational complexity, which are essential for building efficient and effective machine learning models. By understanding the principles of algorithmic efficiency and optimization, Machine Learning Engineers can create models that can learn from data quickly and accurately.
Software Engineer
Software Engineers design, develop, test, and maintain software applications. This course provides a solid foundation in algorithm design and analysis, which is crucial for developing efficient and reliable software. By understanding the principles of algorithmic efficiency, data structures, and optimization techniques, Software Engineers can create high-performing software that meets the needs of users.
Computer Scientist
Computer Scientists design and develop computer software and systems. This course provides a solid foundation in algorithm design, optimization techniques, and computational complexity, which are essential for developing efficient and effective software and systems. By understanding the principles of algorithmic efficiency and optimization, Computer Scientists can create software and systems that can perform complex tasks quickly and accurately.
Operations Research Analyst
Operations Research Analysts use mathematical and statistical modeling techniques to solve complex business problems. This course provides a strong foundation in algorithm design, optimization techniques, and computational complexity, which are essential for developing efficient and effective operations research models. By understanding the principles of algorithmic efficiency and optimization, Operations Research Analysts can create models that can help businesses make better decisions.
Data Scientist
Data Scientists use data analysis and machine learning techniques to extract insights from data. This course provides a strong foundation in algorithmic efficiency and computational complexity, which is essential for designing efficient data analysis and machine learning algorithms. By understanding how different algorithms perform under different conditions, Data Scientists can make informed decisions about which algorithms to use for specific data analysis tasks.
Computer Vision Engineer
Computer Vision Engineers design and develop algorithms for computer vision applications, such as image processing, object recognition, and facial recognition. This course provides a strong foundation in algorithm design, optimization techniques, and computational complexity, which are essential for developing efficient and accurate computer vision algorithms. By understanding the principles of algorithmic efficiency and optimization, Computer Vision Engineers can create models that can process and analyze images and videos quickly and accurately.
Natural Language Processing Engineer
Natural Language Processing Engineers design and develop algorithms for natural language processing tasks, such as machine translation, text classification, and sentiment analysis. This course provides a strong foundation in algorithm design, optimization techniques, and computational complexity, which are essential for developing efficient and accurate natural language processing algorithms. By understanding the principles of algorithmic efficiency and optimization, Natural Language Processing Engineers can create models that can process and analyze text data quickly and accurately.
Quantitative Analyst
Quantitative Analysts combine statistical modeling, programming, and problem-solving skills to help companies make informed decisions. This course in Algorithm Design and Analysis helps build a foundation for developing and analyzing the complex models used in this role. Understanding algorithmic efficiency, computational complexity, and optimization techniques is essential for developing accurate and efficient models that can produce meaningful insights for businesses.
Information Security Analyst
Information Security Analysts design and implement security measures to protect computer systems and networks from unauthorized access and attacks. This course provides a strong foundation in algorithm design, optimization techniques, and computational complexity, which are essential for developing efficient and effective security measures. By understanding the principles of algorithmic efficiency and optimization, Information Security Analysts can create security measures that can protect computer systems and networks from attack.
Actuary
Actuaries use mathematical and statistical modeling techniques to assess risk and uncertainty. This course provides a strong foundation in algorithm design, optimization techniques, and computational complexity, which are essential for developing efficient and accurate actuarial models. By understanding the principles of algorithmic efficiency and optimization, Actuaries can create models that can help them assess risk and make better decisions.
Financial Analyst
Financial Analysts use financial modeling and analysis techniques to make investment decisions. This course provides a solid foundation in algorithm design, optimization techniques, and computational complexity, which are essential for developing efficient and accurate financial models. By understanding the principles of algorithmic efficiency and optimization, Financial Analysts can create models that can help them make better investment decisions.
Statistician
Statisticians use statistical modeling and analysis techniques to extract insights from data. This course provides a strong foundation in algorithm design, optimization techniques, and computational complexity, which are essential for developing efficient and accurate statistical models. By understanding the principles of algorithmic efficiency and optimization, Statisticians can create models that can help them make better decisions.
Game Developer
Game Developers design and develop video games. This course provides a solid foundation in algorithm design, optimization techniques, and computational complexity, which are essential for developing efficient and engaging video games. By understanding the principles of algorithmic efficiency and optimization, Game Developers can create video games that can run smoothly and provide an enjoyable gaming experience.
Technical Writer
Technical Writers create technical documentation, such as user manuals, white papers, and training materials. This course may be useful for developing the technical writing skills needed to create clear and concise technical documents. Understanding algorithmic concepts and computational complexity can help Technical Writers explain complex technical concepts in a way that is easy to understand.
Product Manager
Product Managers are responsible for the planning, development, and marketing of products. This course may be useful for developing the analytical and decision-making skills needed to be a successful Product Manager. Understanding algorithmic efficiency, computational complexity, and optimization techniques can help Product Managers make informed decisions about product features and functionality.

Reading list

We've selected seven books that we think will supplement your learning. Use these to develop background knowledge, enrich your coursework, and gain a deeper understanding of the topics covered in 算法设计与分析 Design and Analysis of Algorithms.
本书是算法与数据结构领域的经典教材,全面介绍了算法和数据结构的基本概念和设计技术,是这门课程的参考书目。
这本参考书以C语言为基础,详细讲解了算法的实现和优化,对于算法实践非常有帮助。对于本课程的进阶学习,它可以提供很好的补充。
这本参考书提供了广泛的算法集合,พร้อม详细的描述和伪代码实现。
这本书提供了算法竞赛的基础知识,包括算法设计和分析的基本概念。对于希望参加算法竞赛或提高算法能力的学生来说,这是一本有用的参考书。
这本书提供了离散数学的基础知识,包括集合论、数论和图论。对于希望理解算法中使用的数学概念的学生来说,这是一本有用的参考书。
这本书提供了数据结构的基本概念,并提供了许多示例和练习。对于希望打牢数据结构基础的学生来说,这是一本很好的参考书。
这本书提供了算法复杂度的深入介绍,包括计算复杂性理论和 NP 完全问题。对于希望深入了解算法复杂性的学生来说,这是一本有用的参考书。

Share

Help others find this course page by sharing it with your friends and followers:
Our mission

OpenCourser helps millions of learners each year. People visit us to learn workspace skills, ace their exams, and nurture their curiosity.

Our extensive catalog contains over 50,000 courses and twice as many books. Browse by search, by topic, or even by career interests. We'll match you to the right resources quickly.

Find this site helpful? Tell a friend about us.

Affiliate disclosure

We're supported by our community of learners. When you purchase or subscribe to courses and programs or purchase books, we may earn a commission from our partners.

Your purchases help us maintain our catalog and keep our servers humming without ads.

Thank you for supporting OpenCourser.

© 2016 - 2024 OpenCourser